Submission #1222162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222162		Aviansh	Two Currencies (JOI23_currencies)	C++20	100 / 100	1960 ms	352820 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define int long long

//persistent segtree

struct segTree{
    struct node{
        int l,r,num,sum;
    };
    node *st;
    node def;
    int cr = 0;
    segTree(int nodes){
        st=new node[nodes];
        def={-1,-1,0,0};
        fill(st,st+nodes,def);
    }

    int cpy(int ind){
        st[++cr]=st[ind];
        return cr;
    }

    int update(int l, int r, int ind, int i, int val){
        if(st[ind].l==-1){
            st[ind].l=++cr;
        }
        if(st[ind].r==-1){
            st[ind].r=++cr;
        }
        if(i<l||i>r){
            return ind;
        }
        //okay must copy now
        ind=cpy(ind);
        if(l==r){
            if(val<0){
                st[ind].num--;
            }
            else{
                st[ind].num++;
            }
            st[ind].sum+=val;
            return ind;
        }
        int mid = (l+r)/2;
        st[ind].l=update(l,mid,st[ind].l,i,val);
        st[ind].r=update(mid+1,r,st[ind].r,i,val);
        st[ind].num=st[st[ind].l].num+st[st[ind].r].num;
        st[ind].sum=st[st[ind].l].sum+st[st[ind].r].sum;
        return ind;
    }

    array<int,2> query(int l, int r, int s, int e, int ind){
        if(st[ind].l==-1){
            st[ind].l=++cr;
        }
        if(st[ind].r==-1){
            st[ind].r=++cr;
        }
        if(e<l||s>r){
            return {0,0};
        }
        if(s<=l&&r<=e){
            return {st[ind].num,st[ind].sum};
        }
        int mid = (l+r)/2;
        array<int,2>ans={0,0};
        array<int,2>lef = query(l,mid,s,e,st[ind].l);
        array<int,2>rig = query(mid+1,r,s,e,st[ind].r);
        ans[0]=lef[0]+rig[0];
        ans[1]=lef[1]+rig[1];
        return ans;
    }
};

const int lg = 20;

int tim=0;

void dfs(int st, vector<array<int,2>>g[], int p, int par[][lg], array<int,2>times[], int dep[], int d){
    par[st][0]=p;
    dep[st]=d;
    for(int i = 1;i<lg;i++){
        par[st][i]=par[par[st][i-1]][i-1];
    }
    times[st][0]=tim++;
    for(array<int,2>e:g[st]){
        if(e[0]==p)
            continue;
        dfs(e[0],g,st,par,times,dep,d+1);
    }
    times[st][1]=tim;
}

int lca(int x, int y, int par[][lg], int dep[]){
    if(dep[x]<dep[y])
        swap(x,y);
    for(int i = lg-1;i>=0;i--){
        if(dep[par[x][i]]>=dep[y]){
            x=par[x][i];
        }
    }
    //at same depth now
    for(int i = lg-1;i>=0;i--){
        if(par[x][i]!=par[y][i]){
            x=par[x][i];
            y=par[y][i];
        }
    }
    if(x==y){
        return x;
    }
    return par[x][0];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,q;
    cin >> n >> m >> q;
    vector<array<int,2>>g[n];
    array<int,2>edges[n-1];
    for(int i = 0;i<n-1;i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        g[a].push_back({b,i});
        g[b].push_back({a,i});
        edges[i]={a,b};
    }
    int par[n][20];
    int dep[n];
    array<int,2>times[n];
    dfs(0,g,0,par,times,dep,0);
    array<int,2>costs[m];
    for(int i = 0;i<m;i++){
        int p,c;
        cin >> p >> c;
        p--;
        int a,b;
        a=edges[p][0];
        b=edges[p][1];
        if(dep[a]>dep[b])
            costs[i]={c,a};
        else{
            costs[i]={c,b};
        }
    }
    sort(costs,costs+m);
    segTree per(1e7);
    vector<int>segs;
    segs.push_back(0);
    //TODO: maybe add build for memory optimisation in segtree
    int las = 0;
    for(array<int,2>check:costs){
        las=per.update(0,n,las,times[check[1]][0],check[0]);
        segs.push_back(per.update(0,n,las,times[check[1]][1],-check[0]));
        las=segs.back();
    }
    while(q--){
        int s,t,x,y;
        cin >> s >> t >> x >> y;
        s--;t--;
        //x is gold, y is silver
        int lc = lca(s,t,par,dep);
        int tot = per.query(0,n,0,times[s][0],las)[0]+per.query(0,n,0,times[t][0],las)[0]-2*per.query(0,n,0,times[lc][0],las)[0];
        x-=tot;
        int lo = 0;
        int hi = m;
        while(lo<hi){
            int mid = (lo+hi+1)/2;
            int ind = segs[mid];
            int sum = per.query(0,n,0,times[s][0],ind)[1]+per.query(0,n,0,times[t][0],ind)[1]-2*per.query(0,n,0,times[lc][0],ind)[1];
            if(sum<=y){
                lo=mid;
            }
            else{
                hi=mid-1;
            }
        }
        lo=segs[lo];
        int did =  per.query(0,n,0,times[s][0],lo)[0]+per.query(0,n,0,times[t][0],lo)[0]-2*per.query(0,n,0,times[lc][0],lo)[0];
        x+=did;
        if(x<0){
            cout << -1 << "\n";
        }
        else{
            cout << x << "\n";
        }
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32