Submission #729598

#	Time	Username	Problem	Language	Result	Execution time	Memory
729598		abcvuitunggio	Two Currencies (JOI23_currencies)	C++17	100 / 100	4321 ms	145576 KiB

currencies

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
    int a,b;
}e[100001];
struct checkpoint{
    int p,c;
}ch[100001];
struct citizen{
    int s,t,x,y,idx;
}c[100001];
struct T{
    int gold,silver;
};
int n,m,q,res[100001];
int p[100001][20],tin[100001],tout[100001],t;//lca
int root[100001],pos[100001],sz[100001],chain[100001],chainsize[100001],id;//hld
int l[100001],r[100001],kq[100001];//binary search
vector <int> ke[100001];
vector <citizen> ve[100001];
vector <T> st[100001];
T operator +(T a, T b){
    return {a.gold+b.gold,a.silver+b.silver};
}
void update(int node, int l, int r, int x, int g, int s, int idx){
    if (l>x||r<x||l>r)
        return;
    if (l==r){
        st[idx][node].gold+=g;
        st[idx][node].silver+=s;
        return;
    }
    int mid=(l+r)>>1;
    update(node<<1,l,mid,x,g,s,idx);
    update(node<<1|1,mid+1,r,x,g,s,idx);
    st[idx][node]=st[idx][node<<1]+st[idx][node<<1|1];
}
void update(int i, int mode){
    if (!i)
        return;
    int u=ch[i].p;
    update(1,1,chainsize[chain[u]],pos[u],(mode?1:-1),(mode?0:ch[i].c),chain[u]);
}
T get(int node, int l, int r, int u, int v, int idx){
    if (l>v||r<u||l>r||u>v)
        return {0,0};
    if (l>=u&&r<=v)
        return st[idx][node];
    int mid=(l+r)>>1;
    return get(node<<1,l,mid,u,v,idx)+get(node<<1|1,mid+1,r,u,v,idx);
}
void dfs(int u=1, int par=1){
    tin[u]=++t;
    sz[u]=1;
    for (int v:ke[u])
        if (v!=par){
            p[v][0]=u;
            for (int i=1;i<20;i++)
                p[v][i]=p[p[v][i-1]][i-1];
            dfs(v,u);
            sz[u]+=sz[v];
        }
    tout[u]=t;
}
bool isancestor(int u, int v){
    return (tin[u]<=tin[v]&&tout[u]>=tout[v]);
}
int lca(int u, int v){
    if (isancestor(u,v))
        return u;
    if (isancestor(v,u))
        return v;
    for (int i=19;i>=0;i--)
        if (p[u][i]&&!isancestor(p[u][i],v))
            u=p[u][i];
    return p[u][0];
}
void dfs2(int u=1){
    if (!pos[u]){
        pos[u]=1;
        root[u]=u;
        chain[u]=++id;
    }
    chainsize[chain[u]]++;
    int mx=0,bigchild=-1;
    for (int v:ke[u])
        if (v!=p[u][0])
            if (mx<sz[v]){
                mx=sz[v];
                bigchild=v;
            }
    if (bigchild!=-1){
        pos[bigchild]=pos[u]+1;
        chain[bigchild]=chain[u];
        root[bigchild]=root[u];
    }
    for (int v:ke[u])
        if (v!=p[u][0])
            dfs2(v);
}
T get(int u, int v){
    int l=lca(u,v);
    T res;
    res.gold=res.silver=0;
    while (u){
        if (isancestor(root[u],l)){
            res=res+get(1,1,chainsize[chain[u]],pos[l]+1,pos[u],chain[u]);
            break;
        }
        res=res+get(1,1,chainsize[chain[u]],1,pos[u],chain[u]);
        u=p[root[u]][0];
    }
    swap(u,v);
    while (u){
        if (isancestor(root[u],l)){
            res=res+get(1,1,chainsize[chain[u]],pos[l]+1,pos[u],chain[u]);
            break;
        }
        res=res+get(1,1,chainsize[chain[u]],1,pos[u],chain[u]);
        u=p[root[u]][0];
    }
    return res;
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> m >> q;
    for (int i=1;i<n;i++){
        cin >> e[i].a >> e[i].b;
        ke[e[i].a].push_back(e[i].b);
        ke[e[i].b].push_back(e[i].a);
    }
    for (int i=1;i<=m;i++)
        cin >> ch[i].p >> ch[i].c;
    sort(ch+1,ch+m+1,[](checkpoint a, checkpoint b){
            return a.c<b.c;
         });
    for (int i=1;i<=q;i++){
        cin >> c[i].s >> c[i].t >> c[i].x >> c[i].y;
        c[i].idx=i;
        l[i]=1;
        r[i]=m;
    }
    dfs();
    dfs2();
    for (int i=1;i<n;i++)
        if (e[i].a==p[e[i].b][0])
            swap(e[i].a,e[i].b);
    for (int i=1;i<=m;i++)
        ch[i].p=e[ch[i].p].a;
    for (int i=1;i<=id;i++)
        st[i].resize(chainsize[i]*4+1);
    while (true){
        bool change=false;
        for (int i=1;i<=id;i++)
            for (T &j:st[i])
                j.gold=j.silver=0;
        for (int i=1;i<=m;i++){
            ve[i].clear();
            update(i,1);
        }
        for (int i=1;i<=q;i++)
            if (l[i]<=r[i]){
                ve[(l[i]+r[i])>>1].push_back(c[i]);
                change=true;
            }
        if (!change)
            break;
        for (int i=1;i<=m;i++){
            update(i,0);
            for (auto j:ve[i]){
                T t=get(j.s,j.t);
                if (t.silver<=j.y){
                    kq[j.idx]=i;
                    l[j.idx]=i+1;
                }
                else
                    r[j.idx]=i-1;
            }
        }
    }
    for (int i=1;i<=id;i++)
        for (T &j:st[i])
            j.gold=j.silver=0;
    for (int i=1;i<=m;i++){
        ve[i].clear();
        update(i,1);
    }
    for (int i=1;i<=q;i++)
        ve[kq[i]].push_back(c[i]);
    for (int i=0;i<=m;i++){
        update(i,0);
        for (auto j:ve[i]){
            T t=get(j.s,j.t);
            res[j.idx]=max(j.x-t.gold,-1LL);
        }
    }
    for (int i=1;i<=q;i++)
        cout << res[i] << '\n';
}

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