laekov

大概是今天不宜刷题来着。应该好好做作业。

用线段树套单调队列可以把复杂度降到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]);

}