Submission #446255

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
446255	2021-07-21T11:06:11 Z	benedict0724	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	94 ms	5492 KB

diameter

#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";
    }
}

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	8 ms	400 KB	Output is correct
5	Correct	34 ms	660 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	252 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	9 ms	332 KB	Output is correct
11	Correct	42 ms	736 KB	Output is correct
12	Correct	3 ms	460 KB	Output is correct
13	Correct	2 ms	460 KB	Output is correct
14	Correct	3 ms	460 KB	Output is correct
15	Correct	12 ms	564 KB	Output is correct
16	Correct	48 ms	1040 KB	Output is correct
17	Correct	33 ms	3948 KB	Output is correct
18	Correct	30 ms	3908 KB	Output is correct
19	Correct	32 ms	3908 KB	Output is correct
20	Correct	42 ms	4216 KB	Output is correct
21	Correct	94 ms	5492 KB	Output is correct