Submission #1262386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262386		ZeroCool	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	411 ms	94432 KiB

diameter

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;;
#define ll long long
#define ar array

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define all(v) v.begin(), v.end()
#define ld long double

const int N = 4e5 + 20;
const int M = 2;
const int LOG = 20;
const ll INF = 1e17;
int MOD = 998244353;

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// //#pragma GCC optimize("unroll-loops")

template<typename T>
inline void chmin(T &x,T y){x = min(x, y);}
template<typename T>
inline void chmax(T &x,T y){x = max(x, y);}
inline void mm(int &x){x = (x % MOD + MOD) % MOD;};

struct Node{
	int da;
	int m2da;
	int dam2dc;
	int m2dcda;
	int ans;

	Node(){
		da = m2da = dam2dc = m2dcda = ans = -INF;
	}

	Node(int x){
		da = x;
		m2da = - 2 * x;
		dam2dc = -x;
		m2dcda = -INF;
		ans = -INF;
	}
};

Node operator+(Node a, Node b){
	Node res;
	res.da = max(a.da, b.da);
	res.m2da = max(a.m2da, b.m2da);
	res.dam2dc = max({a.dam2dc, b.dam2dc, a.da + b.m2da});
	res.m2dcda = max({a.m2dcda, b.m2dcda, a.m2da + b.da});
	res.ans = max({a.ans, b.ans, a.dam2dc + b.da, a.da + b.m2dcda});
	return res;
}

Node s[4 * N];
int lz[4 * N];

void bld(int k,int tl,int tr){
	if(tl == tr){
		s[k] = Node(0);
		return;
	}
	int tm = (tl + tr) / 2;
	bld(k * 2, tl, tm);
	bld(k * 2 + 1, tm + 1, tr);
	s[k] = s[k * 2] + s[k * 2 + 1];
}

void psh(int k,int tl,int tr){
	s[k].da += lz[k];
	s[k].m2da -= 2 * lz[k];
	s[k].dam2dc -= lz[k];
	s[k].m2dcda -= lz[k];
	if(tl != tr){
		lz[k * 2] += lz[k];
		lz[k * 2 + 1] += lz[k];
	}
	lz[k] = 0;
}

void upd(int k,int tl,int tr, int l,int r,int v){
	psh(k, tl, tr);
	if(l > tr || tl > r)return;
	if(l <= tl && tr <= r){
		lz[k] += v;
		psh(k, tl, tr);
		return;
	}
	int tm = (tl + tr) / 2;
	upd(k * 2, tl, tm, l, r, v);
	upd(k * 2 + 1, tm + 1, tr, l, r, v);
	s[k] = s[k * 2] + s[k * 2 +1];
}

int qry(){
	psh(1, 0, 1);
	return s[1].ans;
}

vector<ar<int,2>> g[N];
int da[N];
vector<int> ord;
int ind[N];
void dfs(int x,int p){
	ord.push_back(x);
	for(auto [u, w]: g[x]){
		if(u == p)continue;
		ind[w] = u;
		dfs(u, x);
		ord.push_back(x);
	}
}

void orz(){
	int n, q, w;
	cin>>n>>q>>w;
	int A[n - 1];
	for(int i = 0;i < n - 1;i++){
		int a, b, c;
		cin>>a>>b>>c;
		--a, --b;
		A[i] = c;
		g[a].push_back({b, i});
		g[b].push_back({a, i});
	}
	dfs(0, 0);
	int L[n], R[n];
	memset(L, 0x3f, sizeof L);
	memset(R, -0x3f, sizeof R);
	int m = ord.size();
	for(int i = 0;i < m;i++){
		chmin(L[ord[i]], i);
		chmax(R[ord[i]], i);
	}
	bld(1, 0, m - 1);
	// assert(0);
	for(int i = 0;i < n - 1;i++){
		int x = ind[i];
		upd(1, 0, m - 1, L[x], R[x], A[i]);
	}
	//  cout<<qry()<<'\n';
	int lst = 0;
	while(q--){
		int a, b;
		cin>>a>>b;
		a = (a + lst) % (n - 1);
		b = (b + lst) % w;
		int x = ind[a];
		upd(1, 0, m - 1, L[x], R[x], -A[a]);
		A[a] = b;
		upd(1, 0, m - 1, L[x], R[x], +A[a]);
		lst = qry();
		cout<<lst<<'\n';
	}

}

signed main() { 		
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	//cin>>t;
	while (t--)orz();
}

//I am stupid :D

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