Submission #68307577

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i ++)
#define per(i, s, t) for(int i = (s); i >= (t); i --)
template<typename T, typename T2>
inline void chmin(T &x, T2 &&y) { x = min(x, y); }
template<typename T, typename T2>
inline void chmax(T &x, T2 &&y) { x = max(x, y); }
typedef long long ll;

const int N = 5e5 + 5;

mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
struct node
{
	int ls, rs, sz;
	unsigned int w;
	ll tg, v, mn;
	void init(ll _v) {w = rnd(); sz = 1; v = mn = _v;}
} a[N];
int idx = 0;

void settag(int x, ll v)
{
	a[x].tg += v;
	a[x].v += v;
	a[x].mn += v;
}

void pd(int x)
{
	if(a[x].tg) settag(a[x].ls, a[x].tg), settag(a[x].rs, a[x].tg), a[x].tg = 0;
}

void pu(int x)
{
	a[x].sz = a[a[x].ls].sz + a[a[x].rs].sz + 1;
	a[x].mn = a[x].ls ? a[a[x].ls].mn : a[x].v;
}

// (-inf,v][v+1,inf]
void splitv(int u, ll v, int &x, int &y)
{
	if(!u) return x = y = 0, void();
	pd(u);
	if(a[u].v <= v) x = u, splitv(a[u].rs, v, a[u].rs, y);
	else y = u, splitv(a[u].ls, v, x, a[u].ls);
	pu(u);
}

// [1,pos][pos+1,n]
void splits(int u, int rk, int &x, int &y)
{
    if(!u) return x = y = 0, void();
	pd(u);
    if(a[a[u].ls].sz < rk) x = u, splits(a[u].rs, rk - a[a[u].ls].sz - 1, a[u].rs, y);
    else y = u, splits(a[u].ls, rk, x, a[u].ls);
    pu(u);
}

int merge(int x, int y)
{
	if(!x || !y) return x | y;
	pd(x), pd(y);
	if(a[x].w < a[y].w) return a[x].rs = merge(a[x].rs, y), pu(x), x;
	else return a[y].ls = merge(x, a[y].ls), pu(y), y;
}

int join(int u, int v)
{
    if (!u || !v)
        return u | v;
    ll x = a[u].mn, y = a[v].mn;
	int t;
    if (x <= y)
        splitv(u, y, t, u);
    else
        splitv(v, x, t, v);
    return merge(t, join(u, v));
}


int ans[N];
void getans(int x, int id)
{
	if(a[x].ls) getans(a[x].ls, id);
	ans[x] = id;
	if(a[x].rs) getans(a[x].rs, id);
}

int n, ls[N], rs[N], rt[N];
ll len[N], qq[N];

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	len[1] = len[2] = 1;
	rep(i, 3, n + 2)
	{
		cin >> ls[i] >> rs[i] >> qq[i];
		ls[i] ++, rs[i] ++;
		len[i] = min((ll)2e18, len[ls[i]] + len[rs[i]]);
		rt[i] = i;
		a[i].init(qq[i]);
	}
	per(i, n + 2, 3)
	{
		// cerr << i << " " << ls[i] << " " << rs[i] << " " << a[rt[i]].sz << endl;
		int l, r;
		splitv(rt[i], len[ls[i]], l, r);
		if(r) settag(r, -len[ls[i]]);
		// cerr << a[l].sz << " " << a[r].sz << endl;
		rt[ls[i]] = join(rt[ls[i]], l);
		rt[rs[i]] = join(rt[rs[i]], r);
	}
	getans(rt[1], 0);
	getans(rt[2], 1);
	// cerr << a[rt[1]].sz << " " << a[rt[2]].sz << endl;
	rep(i, 3, n + 2) cout << ans[i] << "\n";

	return 0;
}

Submission Info

Judge Result