Submission #884727

#	Time	Username	Problem	Language	Result	Execution time	Memory
884727		Alish	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	438 ms	31380 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("connect.in" , "r" , stdin) ; freopen("connect.out" , "w" , stdout);


ll mod = 1e9+7 ;

const int N = 1e5+23;
vector<pll> g[N];
int st[N], ft[N], tim, pos[N];
vector<pair<pll, ll> > E;
ll seg[4*N], lpz[4*N];
int n, q;
ll h[N];
ll ans[N];

void dfs(int v, int p=0){
    st[v]=tim++;
    pos[st[v]]=v;
    for (auto pp: g[v]){
        ll u=pp.F, w=pp.S;
        if(u==p) continue;
        h[u]=h[v]+w;
        dfs(u, v);
    }
    ft[v]=tim;
}

void Shift(int l, int r, int ind=0){
    if(r-l==1)return ;
    if(!lpz[ind]) return;
    seg[2*ind+1]+=lpz[ind];
    seg[2*ind+2]+=lpz[ind];
    lpz[2*ind+1]+=lpz[ind];
    lpz[2*ind+2]+=lpz[ind];
    lpz[ind]=0;
}

void build(int l=0, int r=n, int ind=0){

    if(r-l==1){
        seg[ind]=h[pos[l]];
        return ;
    }
    int mid=(r+l)>>1;
    build(l, mid, 2*ind+1); build(mid, r, 2*ind+2);
    seg[ind]=max(seg[2*ind+1], seg[2*ind+2]);
}

void upd(int lx, int rx, ll v, int l=0, int r=n, int ind=0){

    Shift(l, r, ind);
    if(lx>=r || rx<=l)return;
    if(lx<=l && rx>=r){
        seg[ind]+=v;
        lpz[ind]+=v;
        return;
    }
    int mid=(r+l)>>1;
    upd(lx, rx, v, l, mid, 2*ind+1);
    upd(lx, rx, v, mid, r, 2*ind+2);
    seg[ind]=max(seg[2*ind+1], seg[2*ind+2]);

}

ll get(int lx, int rx, int l=0, int r=n, int ind=0){
    Shift(l, r, ind);
    if(lx>=r || rx<=l) return 0;
    if(lx<=l && rx>=r) return seg[ind];
    int mid=(r+l)>>1;
    return max(get(lx, rx, l, mid, 2*ind+1), get(lx, rx, mid, r, 2*ind+2));
}


int main()
{
    //fast_io
    cin>>n>>q>>mod;
    for (int i=0; i<n-1; i++){
        ll u, v, w; cin>>v>>u>>w;
        g[v].pb({u, w}); g[u].pb({v, w});
        E.pb({{v, u}, w});
    }
    dfs(1); build();
    set<pll> stt;
    vector<pll> temp;
    for (auto pp: g[1]){
        ll u=pp.F;
        stt.insert({get(st[u], ft[u]), u});
        temp.pb({st[u], u});
        ans[u]=get(st[u], ft[u]);
    }
    temp.pb({N, N});
    sort(all(temp));


    ll la=0;
    while(q--){
        ll i, w;
        cin>>i>>w;
        i=(i+la)%(n-1);
        w=(w+la)%mod;
        ll v=E[i].F.F, u=E[i].F.S;
        if(st[v]<st[u])swap(u, v);
        upd(st[v], ft[v], w-E[i].S);
        E[i].S=w;
        pll why={st[v], N};

        int t=upper_bound(all(temp), why)-temp.begin()-1;
        pii ch=temp[t];
        auto x=stt.lower_bound(Mp(ans[ch.S], ch.S));
        stt.erase(x);
        ans[ch.S]=get(st[ch.S], ft[ch.S]);
        stt.insert({ans[ch.S], ch.S});

        ll res=0;

        x=stt.end();
        x--;
        res+=x->F;
        if(x!=stt.begin()){
            x--;
            res+=x->F;
        }
        cout<<res<<endl;
        la=res;

    }

}

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