제출 #446255

#제출 시각아이디문제언어결과실행 시간메모리
446255benedict0724Dynamic Diameter (CEOI19_diameter)C++17
7 / 100
94 ms5492 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pl; pl add(pl x, pl y) { pl ans; ans.first = max(x.first, y.first); if(x.first > y.first) ans.second = max(x.second, y.first); else ans.second = max(x.first, y.second); return ans; } pl tree[400002]; int v[100002]; pl init(int i, int l, int r) { if(l == r) return tree[i] = {v[l], 0}; int mid = (l + r)/2; return tree[i] = add(init(i*2, l, mid), init(i*2+1, mid+1, r)); } void update(int i, int l, int r, int idx, int ch) { if(l == r) { tree[i] = {ch, 0}; return; } int m = (l + r)/2; if(idx <= m) update(i*2, l, m, idx, ch); else update(i*2+1, m+1, r, idx, ch); tree[i] = add(tree[i*2], tree[i*2+1]); } int query() { return tree[1].first + tree[1].second; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, q, w; cin >> n >> q >> w; for(int i=0;i<n-1;i++) { int a, b, c; cin >> a >> b >> c; v[i] = c; } init(1, 0, n-2); int last = 0; for(int i=1;i<=q;i++) { int d, e; cin >> d >> e; d = (d + last)%(n-1); e = (e + last)%w; update(1, 0, n-2, d, e); last = query(); cout << last << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...