#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
const int N = 100000, N_ = (1 << 18);
struct node {
ll sum = 0, mind = 0, maxd = 0, max12 = 0, max23 = 0, ans = 0;
node shift(ll x) {
return node{sum + x, mind + x, maxd + x, max12 - x, max23 - x, ans};
}
static node create(char c, ll x) {
if (c == '(') {
return node{x, 0, x, 0, x, x};
} else {
return node{-x, -x, 0, 2 * x, x, x};
}
}
} t[N_ * 2];
node mrg(node a, node b) {
b = b.shift(a.sum);
node c;
c.sum = b.sum;
c.mind = min(a.mind, b.mind);
c.maxd = max(a.maxd, b.maxd);
c.max12 = max({a.max12, b.max12, a.maxd - b.mind * 2});
c.max23 = max({a.max23, b.max23, b.maxd - a.mind * 2});
c.ans = max({a.ans, b.ans, a.max12 + b.maxd, a.maxd + b.max23});
return c;
}
int sz = 1;
string s;
ll W[N];
int op[N], cl[N], idx[N * 2], T = 0;
void init(int n) {
while (sz < n) sz <<= 1;
for (int i = 0; i < n; ++i) {
t[i + sz] = node::create(s[i], W[idx[i]]);
}
for (int i = sz - 1; i > 0; --i) {
t[i] = mrg(t[i << 1], t[i << 1 | 1]);
}
}
void modify(int i) {
t[i + sz] = node::create(s[i], W[idx[i]]);
i += sz;
i >>= 1;
while (i) {
t[i] = mrg(t[i << 1], t[i << 1 | 1]);
i >>= 1;
}
}
vector<pair<int, int>> g[N];
void dfs(int v, int p) {
for (auto [to, i] : g[v]) {
if (to != p) {
op[i] = T++;
idx[op[i]] = i;
s += '(';
dfs(to, v);
cl[i] = T++;
s += ')';
idx[cl[i]] = i;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
ll w;
cin >> w;
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
--a, --b;
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
cin >> W[i];
}
dfs(0, -1);
init(2 * (n - 1));
ll last = 0;
while (q--) {
int i;
ll e;
cin >> i >> e;
i = (i + last) % (n - 1);
W[i] = (e + last) % w;
modify(op[i]), modify(cl[i]);
cout << (last = t[1].ans) << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2696 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2692 KB |
Output is correct |
9 |
Correct |
1 ms |
2688 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2692 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
3 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2696 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2692 KB |
Output is correct |
9 |
Correct |
1 ms |
2688 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2692 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
3 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
5 ms |
2960 KB |
Output is correct |
20 |
Correct |
5 ms |
3028 KB |
Output is correct |
21 |
Correct |
5 ms |
2960 KB |
Output is correct |
22 |
Correct |
5 ms |
3028 KB |
Output is correct |
23 |
Correct |
8 ms |
4308 KB |
Output is correct |
24 |
Correct |
9 ms |
4436 KB |
Output is correct |
25 |
Correct |
8 ms |
4436 KB |
Output is correct |
26 |
Correct |
9 ms |
4756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2692 KB |
Output is correct |
3 |
Correct |
3 ms |
2704 KB |
Output is correct |
4 |
Correct |
10 ms |
2936 KB |
Output is correct |
5 |
Correct |
43 ms |
3844 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2772 KB |
Output is correct |
8 |
Correct |
2 ms |
2772 KB |
Output is correct |
9 |
Correct |
3 ms |
2852 KB |
Output is correct |
10 |
Correct |
13 ms |
3084 KB |
Output is correct |
11 |
Correct |
56 ms |
4088 KB |
Output is correct |
12 |
Correct |
4 ms |
4308 KB |
Output is correct |
13 |
Correct |
4 ms |
4308 KB |
Output is correct |
14 |
Correct |
6 ms |
4308 KB |
Output is correct |
15 |
Correct |
18 ms |
4552 KB |
Output is correct |
16 |
Correct |
77 ms |
5772 KB |
Output is correct |
17 |
Correct |
51 ms |
32312 KB |
Output is correct |
18 |
Correct |
44 ms |
32192 KB |
Output is correct |
19 |
Correct |
45 ms |
32208 KB |
Output is correct |
20 |
Correct |
63 ms |
32336 KB |
Output is correct |
21 |
Correct |
166 ms |
32840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2900 KB |
Output is correct |
2 |
Correct |
9 ms |
3156 KB |
Output is correct |
3 |
Correct |
31 ms |
3652 KB |
Output is correct |
4 |
Correct |
60 ms |
4348 KB |
Output is correct |
5 |
Correct |
7 ms |
5972 KB |
Output is correct |
6 |
Correct |
14 ms |
6100 KB |
Output is correct |
7 |
Correct |
44 ms |
6732 KB |
Output is correct |
8 |
Correct |
86 ms |
7440 KB |
Output is correct |
9 |
Correct |
28 ms |
17656 KB |
Output is correct |
10 |
Correct |
36 ms |
17868 KB |
Output is correct |
11 |
Correct |
74 ms |
18268 KB |
Output is correct |
12 |
Correct |
122 ms |
18544 KB |
Output is correct |
13 |
Correct |
50 ms |
32044 KB |
Output is correct |
14 |
Correct |
61 ms |
32160 KB |
Output is correct |
15 |
Correct |
111 ms |
32420 KB |
Output is correct |
16 |
Correct |
160 ms |
32628 KB |
Output is correct |
17 |
Correct |
181 ms |
32676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
235 ms |
33440 KB |
Output is correct |
2 |
Correct |
221 ms |
33392 KB |
Output is correct |
3 |
Correct |
225 ms |
33372 KB |
Output is correct |
4 |
Correct |
245 ms |
33412 KB |
Output is correct |
5 |
Correct |
208 ms |
33368 KB |
Output is correct |
6 |
Correct |
206 ms |
33672 KB |
Output is correct |
7 |
Correct |
238 ms |
36580 KB |
Output is correct |
8 |
Correct |
218 ms |
36572 KB |
Output is correct |
9 |
Correct |
232 ms |
36572 KB |
Output is correct |
10 |
Correct |
233 ms |
36572 KB |
Output is correct |
11 |
Correct |
226 ms |
36432 KB |
Output is correct |
12 |
Correct |
201 ms |
35872 KB |
Output is correct |
13 |
Correct |
254 ms |
41864 KB |
Output is correct |
14 |
Correct |
239 ms |
41952 KB |
Output is correct |
15 |
Correct |
240 ms |
41964 KB |
Output is correct |
16 |
Correct |
250 ms |
41872 KB |
Output is correct |
17 |
Correct |
257 ms |
41036 KB |
Output is correct |
18 |
Correct |
217 ms |
37704 KB |
Output is correct |
19 |
Correct |
237 ms |
41972 KB |
Output is correct |
20 |
Correct |
237 ms |
41964 KB |
Output is correct |
21 |
Correct |
243 ms |
41980 KB |
Output is correct |
22 |
Correct |
243 ms |
41820 KB |
Output is correct |
23 |
Correct |
245 ms |
41132 KB |
Output is correct |
24 |
Correct |
204 ms |
37676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2696 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2692 KB |
Output is correct |
9 |
Correct |
1 ms |
2688 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2692 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
3 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
5 ms |
2960 KB |
Output is correct |
20 |
Correct |
5 ms |
3028 KB |
Output is correct |
21 |
Correct |
5 ms |
2960 KB |
Output is correct |
22 |
Correct |
5 ms |
3028 KB |
Output is correct |
23 |
Correct |
8 ms |
4308 KB |
Output is correct |
24 |
Correct |
9 ms |
4436 KB |
Output is correct |
25 |
Correct |
8 ms |
4436 KB |
Output is correct |
26 |
Correct |
9 ms |
4756 KB |
Output is correct |
27 |
Correct |
2 ms |
2644 KB |
Output is correct |
28 |
Correct |
2 ms |
2692 KB |
Output is correct |
29 |
Correct |
3 ms |
2704 KB |
Output is correct |
30 |
Correct |
10 ms |
2936 KB |
Output is correct |
31 |
Correct |
43 ms |
3844 KB |
Output is correct |
32 |
Correct |
1 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
2772 KB |
Output is correct |
34 |
Correct |
2 ms |
2772 KB |
Output is correct |
35 |
Correct |
3 ms |
2852 KB |
Output is correct |
36 |
Correct |
13 ms |
3084 KB |
Output is correct |
37 |
Correct |
56 ms |
4088 KB |
Output is correct |
38 |
Correct |
4 ms |
4308 KB |
Output is correct |
39 |
Correct |
4 ms |
4308 KB |
Output is correct |
40 |
Correct |
6 ms |
4308 KB |
Output is correct |
41 |
Correct |
18 ms |
4552 KB |
Output is correct |
42 |
Correct |
77 ms |
5772 KB |
Output is correct |
43 |
Correct |
51 ms |
32312 KB |
Output is correct |
44 |
Correct |
44 ms |
32192 KB |
Output is correct |
45 |
Correct |
45 ms |
32208 KB |
Output is correct |
46 |
Correct |
63 ms |
32336 KB |
Output is correct |
47 |
Correct |
166 ms |
32840 KB |
Output is correct |
48 |
Correct |
2 ms |
2900 KB |
Output is correct |
49 |
Correct |
9 ms |
3156 KB |
Output is correct |
50 |
Correct |
31 ms |
3652 KB |
Output is correct |
51 |
Correct |
60 ms |
4348 KB |
Output is correct |
52 |
Correct |
7 ms |
5972 KB |
Output is correct |
53 |
Correct |
14 ms |
6100 KB |
Output is correct |
54 |
Correct |
44 ms |
6732 KB |
Output is correct |
55 |
Correct |
86 ms |
7440 KB |
Output is correct |
56 |
Correct |
28 ms |
17656 KB |
Output is correct |
57 |
Correct |
36 ms |
17868 KB |
Output is correct |
58 |
Correct |
74 ms |
18268 KB |
Output is correct |
59 |
Correct |
122 ms |
18544 KB |
Output is correct |
60 |
Correct |
50 ms |
32044 KB |
Output is correct |
61 |
Correct |
61 ms |
32160 KB |
Output is correct |
62 |
Correct |
111 ms |
32420 KB |
Output is correct |
63 |
Correct |
160 ms |
32628 KB |
Output is correct |
64 |
Correct |
181 ms |
32676 KB |
Output is correct |
65 |
Correct |
235 ms |
33440 KB |
Output is correct |
66 |
Correct |
221 ms |
33392 KB |
Output is correct |
67 |
Correct |
225 ms |
33372 KB |
Output is correct |
68 |
Correct |
245 ms |
33412 KB |
Output is correct |
69 |
Correct |
208 ms |
33368 KB |
Output is correct |
70 |
Correct |
206 ms |
33672 KB |
Output is correct |
71 |
Correct |
238 ms |
36580 KB |
Output is correct |
72 |
Correct |
218 ms |
36572 KB |
Output is correct |
73 |
Correct |
232 ms |
36572 KB |
Output is correct |
74 |
Correct |
233 ms |
36572 KB |
Output is correct |
75 |
Correct |
226 ms |
36432 KB |
Output is correct |
76 |
Correct |
201 ms |
35872 KB |
Output is correct |
77 |
Correct |
254 ms |
41864 KB |
Output is correct |
78 |
Correct |
239 ms |
41952 KB |
Output is correct |
79 |
Correct |
240 ms |
41964 KB |
Output is correct |
80 |
Correct |
250 ms |
41872 KB |
Output is correct |
81 |
Correct |
257 ms |
41036 KB |
Output is correct |
82 |
Correct |
217 ms |
37704 KB |
Output is correct |
83 |
Correct |
237 ms |
41972 KB |
Output is correct |
84 |
Correct |
237 ms |
41964 KB |
Output is correct |
85 |
Correct |
243 ms |
41980 KB |
Output is correct |
86 |
Correct |
243 ms |
41820 KB |
Output is correct |
87 |
Correct |
245 ms |
41132 KB |
Output is correct |
88 |
Correct |
204 ms |
37676 KB |
Output is correct |
89 |
Correct |
215 ms |
32764 KB |
Output is correct |
90 |
Correct |
215 ms |
33280 KB |
Output is correct |
91 |
Correct |
216 ms |
34876 KB |
Output is correct |
92 |
Correct |
240 ms |
34832 KB |
Output is correct |
93 |
Correct |
234 ms |
38008 KB |
Output is correct |
94 |
Correct |
230 ms |
36660 KB |
Output is correct |
95 |
Correct |
233 ms |
38828 KB |
Output is correct |
96 |
Correct |
256 ms |
37448 KB |
Output is correct |
97 |
Correct |
247 ms |
38740 KB |
Output is correct |
98 |
Correct |
240 ms |
41552 KB |
Output is correct |
99 |
Correct |
266 ms |
38540 KB |
Output is correct |
100 |
Correct |
265 ms |
38356 KB |
Output is correct |