Submission #1106480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106480		Octagons	Tree (IOI24_tree)	C++17	59 / 100	2068 ms	50356 KiB

tree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
long long L, R, w[N];
vector<int> adj[N];
int n, pr[N], x[N], in[N], sz[N], idx;
int srtx[N], rv[N];
bool f;
pair<int, ll> srtox[N];
ll srtx2[N];

struct node {
	pair<int, int> mn;
	ll sm;
} t[(1 << 19)];

void build(int l, int r, int x) {
	if (l == r) {
		t[x].sm = 0;
		t[x].mn = {w[rv[l]], l};
		if (adj[rv[l]].empty())t[x].mn = {int(1e9), int(1e9)};
		return;
	}
	int m = (l + r) >> 1;
	build(l, m, x*2+1);
	build(m+1, r, x*2+2);
	t[x].sm = 0;
	t[x].mn = min(t[x*2+1].mn, t[x*2+2].mn);
}

void upd(int l, int r, int x, int i, ll v) {
	t[x].sm -= v;
	if (l == r)return;
	int m = (l + r) >> 1;
	if (i <= m) {
		upd(l, m, x*2+1, i, v);
	} else {
		upd(m+1, r, x*2+2, i, v);
	}
}

ll getsm(int li, int ri, int x, int l, int r) {
	if (li >= l && ri <= r)return t[x].sm;
	if (li > r || ri < l)return 0;
	int m = (li + ri) >> 1;
	return getsm(li, m, x*2+1, l, r) + getsm(m+1, ri, x*2+2, l, r);
}
pair<int, int> geti(int li, int ri, int x, int l, int r) {
	if (li >= l && ri <= r)return t[x].mn;
	if (li > r || ri < l)return {int(1e9), int(1e9)};
	int m = (li + ri) >> 1;
	return min(geti(li, m, x*2+1, l, r), geti(m+1, ri, x*2+2, l, r));
}

void rem(int li, int ri, int x, int l, int r) {
	if (t[x].mn.first == 1e9)return;
	if (li > r || ri < l)return;
	if (li == ri) {
		t[x].mn = {int(1e9), int(1e9)};
		return;
	}
	int m = (li + ri) >> 1;
	rem(li, m, x*2+1, l, r);
	rem(m+1, ri, x*2+2, l, r);
	t[x].mn = min(t[x*2+1].mn, t[x*2+2].mn);
}
ll bit[int(1e6+1)];
void init(int u) {
	x[u] = (adj[u].empty());
	rv[idx] = u;
	in[u] = idx++;
	sz[u] = 1;
	for (auto &v : adj[u]) {
		init(v);
		x[u] += x[v];
		sz[u] += sz[v];
	}
	if (w[u] == 0) {
		x[u] = 1;
	}
}
ll lf;


ll getb(int i) {
	ll ret = 0;
	while (i) {
		ret += bit[i];
		i -= (i & -i);
	}
	return ret;
}

void updop(int i, ll v) {
	while (i <= 1e6) {
		bit[i] += v;
		i += (i & -i);
	}
}

void updb(int lo, int ro, ll v) {
	if (lo > ro)return;
	updop(lo, v);
	updop(ro+1, -v);
}

int id[N];

bool cmp(int i, int j) {
	return (x[i] < x[j]);
}

void init(vector<int> P, vector<int> W) {
	n = P.size();
	f = true;
	idx = 0;
	lf = 0;
	for (int i = 0; i < n; i++) {
		adj[i].clear();
		w[i] = W[i];
		pr[i] = P[i];
		f &= (w[i] <= 1);
	}
	for (int i = 1; i < n; i++) {
		adj[P[i]].push_back(i);
	}
	init(0);
	for (int i = 0; i < n; i++) {
		srtx[i] = x[i];
		if (adj[i].empty())lf += w[i];
		srtox[i] = {x[i], w[i]};
	}
	sort(srtox, srtox+n);
	sort(srtx, srtx+n);
	ll smr = 0, smr2 = 0;
	for (int i = 0; i < n; i++) {
		id[i] = i;
	}
	sort(id, id+n, cmp);
	for (int i = n-1; i >= 0; i--) {
		smr += srtox[i].second;
		srtox[i].second = smr;
		if (id[i] == 0) {
			smr2 += 0;
		} else {
			smr2 += w[pr[id[i]]];
		}
		srtx2[i] = smr2;
	}
	srtx2[n] = srtox[n].second = 0;
	for (int i = 0; i <= 1e6; i++) {
		bit[i] = 0;
	}
	for (int i = 1; i < n; i++) {
		if (x[pr[i]] > x[i])updb(x[i], x[pr[i]]-1, w[pr[i]] * x[i]);
	}
}
ll ans;

void dfs(int u) {
	if (adj[u].empty()) {
		ans += L * w[u];
		upd(0, n-1, 0, in[u], -L);
		return;
	}
	for (auto &v : adj[u]) {
		dfs(v);
	}
	ll xx = getsm(0, n-1, 0, in[u], in[u] + sz[u] - 1);
	while (xx > R) {
		ll nedi = xx - R;
		pair<int, int> mno = geti(0, n-1, 0, in[u], in[u] + sz[u] - 1);
		ll xo = getsm(0, n-1, 0, mno.second, mno.second + sz[rv[mno.second]] - 1);
		if (xo == L) {
			rem(0, n-1, 0, mno.second, mno.second + sz[rv[mno.second]] - 1);
			continue;
		}
		if (xo - L >= nedi) {
			ans += nedi * w[rv[mno.second]];
			upd(0, n-1, 0, mno.second, nedi);
			rem(0, n-1, 0, mno.second + 1, mno.second + sz[rv[mno.second]] - 1);
			break;
		}
		xx -= (xo - L);
		ans += (xo - L) * w[rv[mno.second]];
		upd(0, n-1, 0, mno.second, xo - L);
		rem(0, n-1, 0, mno.second, mno.second + sz[rv[mno.second]] - 1);
	}
}

long long query(int lo, int ro) {
	L = lo, R = ro;
	if (f) {
		ans = L * lf;
		ll sb = max(1ll, (R / L) - 1ll);
		while ((sb + 1ll) * L <= R)sb++;
		int id = upper_bound(srtx, srtx+n, sb) - srtx;
		ans -= R * srtox[id].second;
		ans += R * srtx2[id];
		ans += L * getb(sb);
		return ans;
	}
	build(0, n-1, 0);
	ans = 0;
	dfs(0);
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 7 / 7
• Subtask 5: 11 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19