Submission #1245521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245521		BlockOG	Dynamic Diameter (CEOI19_diameter)	C++20	7 / 100	158 ms	7992 KiB

diameter

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

pair<pair<int, int>, long long> edges[99999];
multiset<long long> top2;

int main() {
    int n, q;
    long long w;
    cin >> n >> q >> w;
    fo(i, 0, n - 1) {
        cin >> edges[i].f.f >> edges[i].f.s >> edges[i].s;
        top2.insert(edges[i].s);
    }

    long long last = 0;
    while (q--) {
        long long d, e;
        cin >> d >> e;

        d = (d + last) % (n - 1);
        e = (e + last) % w;

        top2.erase(top2.lb(edges[d].s));
        edges[d].s = e;
        top2.insert(e);

        long long res = 0;
        auto it = top2.rbegin();
        res += *it;
        it++;
        if (it != top2.rend()) res += *it;

        cout << res << endl;
        last = res;
    }
}

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