大概是今天不宜刷题来着。应该好好做作业。
用线段树套单调队列可以把复杂度降到O(nlogn)。然后deque严重不靠谱，得用list才行。
然后还是跑得巨慢。前面的人是排序搞定的么？表示不明觉厉。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <deque>
#include <list>
#include <algorithm>
using namespace std;
int _d_;
#define readInt(_x_) { \
int& _s_ = _x_; \
while (!isdigit(_d_ = getchar())); \
_s_ = 0; \
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \
}
//typedef deque <int> dque_i;
typedef list <int> dque_i;
struct seg {
int l, r;
dque_i u, d;
seg *ls, *rs;
};
const int maxn = 250009;
const int maxm = 500009;
const int inf = 0x3f3f3f3f;
int n, l, m, x[maxn], y[maxn], d[maxn], f[maxn], *r[maxm];
seg *rt, *sp;
inline bool cmpP(int* a, int* b) {
return *a < *b;
}
void dispVals() {
int t = (n - 1) << 1;
sort(r, r + t, cmpP);
m = 0;
for (int i = 0, l = *r[0] - 1; i < t; ++ i)
if (*r[i] == l)
*r[i] = m;
else
l = *r[i], *r[i] = ++ m;
}
int upQue(dque_i& q, int d0) {
while (!q. empty() && d0 - d[q. front()] > l)
q. pop_front();
if (q. empty())
return n;
else
return q. front();
}
void insQue(dque_i& q, int i) {
while (!q. empty() && f[i] <= f[q. back()])
q. pop_back();
q. push_back(i);
}
#define mid(p) ((p->l+p->r)>>1)
inline seg* sgtBuild(int l, int r) {
seg* p = sp ++;
p-> l = l;
p-> r = r;
if (l + 1 < r) {
p-> ls = sgtBuild(l, mid(p));
p-> rs = sgtBuild(mid(p), r);
}
return p;
}
inline int sgtQry(seg* p, int l, int r, int d) {
int x = upQue(p-> u, d), y, z;
if (p-> l == l && p-> r == r)
y = upQue(p-> d, d);
else if (r <= mid(p))
y = sgtQry(p-> ls, l, r, d);
else if (l >= mid(p))
y = sgtQry(p-> rs, l, r, d);
else {
y = sgtQry(p-> ls, l, mid(p), d);
z = sgtQry(p-> rs, mid(p), r, d);
if (f[z] < f[y])
y = z;
}
if (f[x] < f[y])
return x;
else
return y;
}
inline void sgtChg(seg* p, int l, int r, int v) {
insQue(p-> d, v);
if (p-> l == l && p-> r == r)
insQue(p-> u, v);
else if (r <= mid(p))
sgtChg(p-> ls, l, r, v);
else if (l >= mid(p))
sgtChg(p-> rs, l, r, v);
else {
sgtChg(p-> ls, l, mid(p), v);
sgtChg(p-> rs, mid(p), r, v);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(n);
readInt(l);
for (int i = 1; i < n; ++ i) {
readInt(x[i]);
readInt(y[i]);
readInt(d[i]);
r[(i << 1) - 2] = x + i;
r[(i << 1) - 1] = y + i;
}
dispVals();
f[0] = 0;
f[n] = inf;
sp = new seg[m * 3];
rt = sgtBuild(1, m + 1);
for (int i = 1; i < n; ++ i) {
if (d[i] <= l)
f[i] = 1;
else
f[i] = f[sgtQry(rt, x[i], y[i] + 1, d[i])] + 1;
if (f[i] < inf)
sgtChg(rt, x[i], y[i] + 1, i);
}
for (int i = 1; i < n; ++ i)
if (f[i] >= inf)
puts("-1");
else
printf("%d\n", f[i]);
}