Submission #445707

#	Time	Username	Problem	Language	Result	Execution time	Memory
445707		Haruto810198	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	819 ms	77188 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

#define Data_Structures
#ifdef Data_Structures
#define V st[cidx]
#define LC st[cidx*2]
#define RC st[cidx*2+1]
#define lsb(x) ((x)&(-(x)))
#endif

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 100010;

/// vertices: 1-indexed
/// edges: 0-indexed

int n, q, W;
vector<vi> edge[MAX]; /// to, w, idx
int el[MAX], er[MAX];
int eval[MAX];
int qd[MAX], qe[MAX];
int res[MAX];
int arr[2*MAX];

int from[MAX], to[MAX];

int stamp = 0;

void dfs(int v, int pv, int dep){

    from[v] = to[v] = stamp;
    arr[stamp] = dep;
    stamp++;

    for(vi e : edge[v]){

        int i = e[0];
        if(i==pv) continue;

        dfs(i, v, dep + e[1]);

        el[e[2]] = from[i];
        er[e[2]] = to[i];

        to[v] = stamp;
        arr[stamp] = dep;
        stamp++;

    }

}

struct Node{
    int sl, sr;
    int Max, Min, ul, lv, ulv;
    int tag;
};

Node st[8*MAX];

void build(int cidx, int cl, int cr){
    V.sl = cl;
    V.sr = cr;
    V.Max = 0;
    V.Min = 0;
    V.ul = 0;
    V.lv = 0;
    V.ulv = 0;
    if(cl < cr){
        int mid = (cl + cr) / 2;
        build(cidx*2, cl, mid);
        build(cidx*2+1, mid+1, cr);
    }
}

void push_tag(int cidx){
    V.Max += V.tag;
    V.Min += V.tag;
    V.ul -= V.tag;
    V.lv -= V.tag;
    if(V.sl < V.sr){
        LC.tag += V.tag;
        RC.tag += V.tag;
    }
    V.tag = 0;
}

void pull(int cidx){
    push_tag(cidx);
    if(V.sl < V.sr){
        push_tag(cidx*2);
        push_tag(cidx*2+1);
        V.Max = max(LC.Max, RC.Max);
        V.Min = min(LC.Min, RC.Min);
        V.ul = max({LC.ul, RC.ul, LC.Max - 2*RC.Min});
        V.lv = max({LC.lv, RC.lv, -2*LC.Min + RC.Max});
        V.ulv = max({LC.ulv, RC.ulv, LC.ul + RC.Max, LC.Max + RC.lv});
    }
}

void modify(int cidx, int ml, int mr, int val){
    if(mr<V.sl or V.sr<ml){
        return;
    }
    if(ml<=V.sl and V.sr<=mr){
        V.tag += val;
        return;
    }
    push_tag(cidx);
    modify(cidx*2, ml, mr, val);
    modify(cidx*2+1, ml, mr, val);
    pull(cidx);
}

int query(){
    return st[1].ulv;
}

void debug(int cidx){

    if(cidx==1){
        cerr<<"debug : ";
    }

    push_tag(cidx);
    pull(cidx);

    if(V.sl < V.sr){
        debug(cidx*2);
        debug(cidx*2+1);
    }
    else{
        cerr<<V.Max<<" ";
    }

    if(cidx==1){
        cerr<<endl;
    }
}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q>>W;

    FOR(i, 0, n-2, 1){
        int u, v, w;
        cin>>u>>v>>w;
        edge[u].pb({v, w, i});
        edge[v].pb({u, w, i});
        eval[i] = w;
    }

    dfs(1, -1, 0);
    build(1, 0, 2*n-2);

    FOR(i, 0, n-2, 1){
        modify(1, el[i], er[i], eval[i]);
    }

    //debug(1);

    FOR(i, 0, q-1, 1){
        cin>>qd[i]>>qe[i];

        int last = 0;
        if(i > 0) last = res[i-1];

        qd[i] = (qd[i] + last) % (n-1);
        qe[i] = (qe[i] + last) % W;

        int delta = qe[i] - eval[qd[i]];
        eval[qd[i]] = qe[i];
        modify(1, el[qd[i]], er[qd[i]], delta);

        res[i] = query();
        //debug(1);

    }

    FOR(i, 0, q-1, 1){
        cout<<res[i]<<'\n';
    }

    return 0;

}

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