Submission #874819

#	Time	Username	Problem	Language	Result	Execution time	Memory
874819		Mizo_Compiler	Arboras (RMI20_arboras)	C++17	0 / 100	5052 ms	34916 KiB

arboras

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 1e5+5, M = 1e9+7;
int n, in[N], id = 0, sz[N], rin[N], dep[N];
vector<int> adj[N];
pair<ll, ll> mx[(1 << 18)];
ll lz[(1 << 18)], sd = 0, p[N][18], fr[N], in2[N];
ll sum[(1 << 18)], st[(1 << 18)], sum2[(1 << 18)], st2[(1 << 18)];
bool tak[(1 << 18)], tak2[(1 << 18)];

ll mul(ll a, ll b) {
	return (a * b) % M;
}

ll add(ll a, ll b) {
	a += b;
	return (a >= M ? a-M : a);
}

ll sub(ll a, ll b) {
	a -= b;
	return (a < 0 ? a+M : a);
}

void prop(int l, int r, int x) {
	mx[x].F += lz[x];
	if (l != r) {
		lz[x*2+1] += lz[x];
		lz[x*2+2] += lz[x];
	}
	lz[x] = 0;
}

void upd(int li, int ri, int x, int l, int r, ll val) {
	if (li >= l && ri <= r) {
		lz[x] += val;
		prop(li, ri, x);
		return;
	}
	prop(li, ri, x);
	if (li > r || ri < l)return;
	int m = (li + ri) >> 1;
	upd(li, m, x*2+1, l, r, val);
	upd(m+1, ri, x*2+2, l, r, val);
	mx[x] = max(mx[x*2+1], mx[x*2+2]);
}


pair<ll, ll> get(int li, int ri, int x, int l, int r) {
	prop(li, ri, x);
	if (li >= l && ri <= r)return mx[x];
	if (li > r || ri < l)return {0, 0};
	int m = (li + ri) >> 1;
	return max(get(li, m, x*2+1, l, r), get(m+1, ri, x*2+2, l, r));
}

int lift(int u, int k) {
	for (int i = 0; i < 18; i++) {
		if ((k & (1 << i)))u = p[u][i];
	}
	return u;
}

int pr(int u, int v) {
	return lift(v, dep[v]-dep[u]-1);
}

void init(int u) {
	rin[id] = u;
	in[u] = id++;
	sz[u] = 1;
	for (auto &v : adj[u]) {
		p[v][0] = u;
		for (int i = 1; i < n; i++) {
			p[v][i] = p[p[v][i-1]][i-1];
		}
		dep[v] = dep[u]+1;
		init(v);
		sz[u] += sz[v];
	}
}

void prop2(int l, int r, int x) {
	if (tak[x]) {
		if (tak2[x]) {
			tak[x] = tak2[x] = false;
			if (l != r) {
				tak2[x*2+1] = tak2[x*2+2] = true;
			}
		} else {
			if (l != r)tak[x*2+1] = tak[x*2+2] = true;
			sum2[x] = sum[x];
		}
	}
	if (~st[x]) {
		sum[x] = mul(r-l+1, st[x]);
		if (l != r) {
			st[x*2+1] = st[x*2+2] = st[x];
		}
		st[x] = -1;
	}
	if (~st2[x]) {
		sum2[x] = mul(r-l+1, st2[x]);
		if (l != r) {
			st2[x*2+1] = st2[x*2+2] = st2[x];
		}
		st2[x] = -1;
	}
}

ll get2(int li, int ri, int x, int l, int r) {
	prop2(li, ri, x);
	if (li >= l && ri <= r)return sum[x];
	if (li > r || ri < l)return 0;
	int m = (li + ri) >> 1;
	return add(get2(li, m, x*2+1, l, r), get2(m+1, ri, x*2+2, l, r));
}

void upd2(int li, int ri, int x, int l, int r, ll val) {
	prop2(li, ri, x);
	if (li >= l && ri <= r) {
		//cout << li << " " << ri << " " << sum[x] << " " << sum2[x] << " ";
		st[x] = val;
		tak[x] = true;
		tak2[x] = false;
		prop2(li, ri, x);
		//cout << sum[x] << " " << sum2[x] << " " << val << "\n";
		return;
	}
	if (li > r || ri < l)return;
	int m = (li + ri) >> 1;
	upd2(li, m, x*2+1, l, r, val);
	upd2(m+1, ri, x*2+2, l, r, val);
	sum[x] = add(sum[x*2+1], sum[x*2+2]);
}

void upd3(int li, int ri, int x, int l, int r, ll val) {
	prop2(li, ri, x);
	if (li >= l && ri <= r) {
		st2[x] = val;
		tak2[x] = false;
		prop2(li, ri, x);
		return;
	}
	if (li > r || ri < l)return;
	int m = (li + ri) >> 1;
	upd3(li, m, x*2+1, l, r, val);
	upd3(m+1, ri, x*2+2, l, r, val);
	sum2[x] = add(sum2[x*2+1], sum2[x*2+2]);
}

void hld_init(int u) {
	in2[u] = id++;
	if (adj[u].empty())return;
	int hc, mx = 0;
	for (auto &v : adj[u]) {
		if (sz[v] > mx) {
			mx = sz[v];
			hc = v;
		}
	}
	fr[hc] = fr[u];
	hld_init(hc);
	for (auto &v : adj[u]) {
		if (v == hc)continue;
		fr[v] = v;
		hld_init(v);
	}
}

void hld_upd(int u, int v, ll val) {
	val %= M;
	//cout << "ace " << u << " " << v<< "\n";
	while (fr[u] != fr[v]) {
		if (in2[u] < in2[v])swap(u, v);
		upd2(0, n-1, 0, in2[fr[u]], in2[u], val);
		u = p[fr[u]][0];
	}
	upd2(0, n-1, 0, min(in2[u], in2[v]), max(in2[u], in2[v]), val);
} 

void hld_upd2(int u, int v, ll val) {
	val %= M;
	while (fr[u] != fr[v]) {
		if (in2[u] < in2[v])swap(u, v);
		upd3(0, n-1, 0, in2[fr[u]], in2[u], val);
		u = p[fr[u]][0];
	}
	upd3(0, n-1, 0, min(in2[u], in2[v]), max(in2[u], in2[v]), val);
} 

void build(int l, int r, int x) {
	if (l == r) {
		mx[x].S = rin[l];
		return;
	}
	int m = (l + r) >> 1;
	build(l, m, x*2+1);
	build(m+1, r, x*2+2);
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < (1 << 18); i++) {
		st[i] = st2[i] = -1;
	}
	for (int i = 1; i < n; i++) {
		int par;
		cin >> par;
		adj[par].pb(i);
	}
	init(0);
	build(0, n-1, 0);
	id = 0;
	hld_init(0);
	for (int i = 1; i < n; i++) {
		int u = i;
		ll ad;
		cin >> ad;
		int anc = u;
		ll maxi = get(0, n-1, 0, in[u], in[u]+sz[u]-1).F;
		for (int i = 17; i >= 0; i--) {
			if (get(0, n-1, 0, in[p[anc][i]], in[p[anc][i]] + sz[p[anc][i]]-1).F < ad+maxi) {
				anc = p[anc][i];
			}
		}
		if (anc != u)hld_upd(p[u][0], anc, maxi+ad);
		int tmp = anc;
		for (int i = 17; i >= 0; i--) {
			pair<ll, ll> xx = get(0, n-1, 0, in[p[anc][i]], in[p[anc][i]] + sz[p[anc][i]]-1);
			int xi = pr(xx.S, p[anc][i]);
			ll val = max(get(0, n-1, 0, in[p[anc][i]], in[xi]-1).F, get(0, n-1, 0, in[xi]+1, in[p[anc][i]] + sz[p[anc][i]]-1).F);
			if (val < ad+maxi) {
				anc = p[anc][i];
			}
		}
		if (anc != tmp)hld_upd2(p[tmp][0], anc, maxi+ad);
		upd(0, n-1, 0, in[u], in[u]+sz[u]-1, ad);
	}
	cout << sub(add(sum[0], sum2[0]), sd) << "\n";
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int u;
		ll ad;
		cin >> u >> ad;
		int anc = u;
		ll maxi = get(0, n-1, 0, in[u], in[u]+sz[u]-1).F;
		for (int i = 17; i >= 0; i--) {
			if (get(0, n-1, 0, in[p[anc][i]], in[p[anc][i]] + sz[p[anc][i]]-1).F < ad+maxi) {
				anc = p[anc][i];
			}
		}
		if (anc != u)hld_upd(p[u][0], anc, maxi+ad);
		int tmp = anc;
		for (int i = 17; i >= 0 && anc; i--) {
			pair<ll, ll> xx = get(0, n-1, 0, in[p[anc][i]], in[p[anc][i]] + sz[p[anc][i]]-1);
			int xi = pr(p[anc][i], xx.S);
			ll val = max(get(0, n-1, 0, in[p[anc][i]], in[xi]-1).F, get(0, n-1, 0, in[xi]+sz[xi], in[p[anc][i]] + sz[p[anc][i]]-1).F);
			//if (!i)cout << xx.F << " " << xx.S << " " << xi << " " << val << "\n";
			if (val < ad+maxi) {
				anc = p[anc][i];
			}
		}
		if (anc != tmp)hld_upd2(p[tmp][0], anc, maxi+ad);
		ll xxx = get(0, n-1, 0, in[u], in[u]).F;
		sd = (sd + xxx) % M;
		upd(0, n-1, 0, in[u], in[u]+sz[u]-1, ad);
		cout << sub(add(sum2[0], sum[0]), sd) << "\n";
	}	
}

Compilation message (stderr)

arboras.cpp: In function 'void hld_init(int)':
arboras.cpp:172:3: warning: 'hc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  172 |   if (v == hc)continue;
      |   ^~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 31
• Subtask 4: 0 / 45