Submission #446255

#	Time	Username	Problem	Language	Result	Execution time	Memory
446255		benedict0724	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	94 ms	5492 KiB

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
• Subtask 2: 0 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27