Submission #1262635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262635		EntityPlantt	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	200 ms	62604 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 1e5, S = 524287;
int64_t w, wg[N], lz[2 * S + 1], ans;
struct sgtdata {
	int64_t d, m2dl, dam2dl, m2dlpdb, ans;
	sgtdata(int64_t l = 0) {
		d = l;
		m2dl = -2 * l;
		dam2dl = m2dlpdb = -l;
	}
	sgtdata(const sgtdata &l, const sgtdata &r) {
		d = max(l.d, r.d);
		m2dl = max(l.m2dl, r.m2dl);
		dam2dl = max(max(l.dam2dl, r.dam2dl), l.d + r.m2dl);
		m2dlpdb = max(max(l.m2dlpdb, r.m2dlpdb), l.m2dl + r.d);
		ans = max(max(l.ans, r.ans), max(l.d + r.m2dlpdb, l.dam2dl + r.d));
	}
} sgt[2 * S + 1];
vector<pair<int, int>> g[N];
int in[N], out[N], tour[3 * N], tourprog, ea[N], eb[N];

void maketour(int u, int p, int64_t d) {
	tour[in[u] = tourprog++] = u;
	auto &sg = sgt[S + in[u]];
	sg = sgtdata(d);
	for (auto &[v, e] : g[u]) {
		if (v == p) continue;
		maketour(v, u, d + wg[e]);
		sgt[S + tourprog] = sg;
		tour[tourprog++] = u;
	}
	out[u] = tourprog - 1;
}
inline void sgtupdlz(int node) {
	if (!lz[node]) return;
	if (node < S) {
		lz[2 * node + 1] += lz[node];
		lz[2 * node + 2] += lz[node];
	}
	sgt[node].d += lz[node];
	sgt[node].m2dl -= lz[node] << 1;
	sgt[node].dam2dl -= lz[node];
	sgt[node].m2dlpdb -= lz[node];
	lz[node] = 0;
}
inline void sgtbuild(int node) {
	if (node >= S) return;
	sgtupdlz(2 * node + 1);
	sgtupdlz(2 * node + 2);
	sgt[node] = sgtdata(sgt[2 * node + 1], sgt[2 * node + 2]);
}
void sgtupd(int l, int r, int64_t deltarune, int node, int cl, int cr) {
	if (r < cl || cr < l) return;
	sgtupdlz(node);
	if (l <= cl && cr <= r) return lz[node] += deltarune, sgtupdlz(node);
	const int cm = cl + cr >> 1;
	sgtupd(l, r, deltarune, 2 * node + 1, cl, cm);
	sgtupd(l, r, deltarune, 2 * node + 2, cm + 1, cr);
	sgtbuild(node);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m >> w;
	for (int i = 0; i < n - 1; i++) {
		cin >> ea[i] >> eb[i] >> wg[i];
		g[--ea[i]].push_back({--eb[i], i});
		g[eb[i]].push_back({ea[i], i});
	}
	maketour(0, 0, 0);
	for (int i = S - 1; i >= 0; i--) sgtbuild(i);
	while (m--) {
		int d;
		int64_t e;
		cin >> d >> e;
		d = (d + ans) % (n - 1);
		e = (e + ans) % w;
		const int nd = max(ea[d], eb[d], [](int a, int b) { return in[a] < in[b]; });
		sgtupd(in[nd], out[nd], e - wg[d], 0, 0, S);
		wg[d] = e;
		cout << (ans = sgt->ans) << '\n';
	}
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27