Submission #1192521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192521		adhityamv	Two Currencies (JOI23_currencies)	C++20	100 / 100	3791 ms	338604 KiB

currencies

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;
#define int long long
#define mp make_pair
#define fi first
#define pii pair<int,int>
#define se second
const int INF=1000000000000000000;
//const int INF=1e9;
const int N=1000000;
//const int M=998244353;
const int ln=20;
template<typename T>
std::ostream& operator<< (std::ostream& os,pair<T,T> p){
    return os << p.fi << "," << p.se << " ";
}
pii operator+ (pii p1, pii p2){
    return (mp(p1.fi+p2.fi,p1.se+p2.se));
}
pii operator- (pii p1,pii p2){
    return (mp(p1.fi-p2.fi,p1.se-p2.se));
}
pii& operator+=(pii& p1,pii p2){
    p1=p1+p2;
    return p1;
}
// this will allow point updates and range queries
struct Node{
    pii vc;
    int li;
    int ri;
    Node* lnode=NULL;
    Node* rnode=NULL;
    Node(int ind,pii valcnt){
        li=ri=ind;
        vc=valcnt;
    }
    Node(Node* l1,Node*r1){
        lnode=l1;
        rnode=r1;
        assert(lnode->ri+1==rnode->li);
        li=lnode->li;
        ri=rnode->ri;
        vc=l1->vc+r1->vc;
    }
    pii query(int l,int r){
        if(l<=li && ri<=r) return vc;
        if(ri<l || li>r) return mp(0,0);
        return (lnode->query(l,r))+(rnode->query(l,r));
    }
    Node* update(int l,pii avc){
        assert(li<=l && l<=ri);
        if(li==ri){
            return new Node(l,vc+avc);
        }
        if(l<=lnode->ri){
            return new Node(lnode->update(l,avc),rnode);
        } else{
            return new Node(lnode,rnode->update(l,avc));
        }
    }
};
vector<Node*> node;
pii query(int l,int r,int t){
    return node[t]->query(l,r);
}
Node* Build(int l,int r){
    if(l==r){
        return new Node(l,mp(0,0));
    }
    int m=(l+r)/2;
    return new Node(Build(l,m),Build(m+1,r));
}
void update(int l,pii avc){
    node.push_back(node.back()->update(l,avc));
}
void init(int n){
    node.push_back(Build(0,n));
}



int pow2[N];
vector<int> edges[N];
vector<int> et;
int parent[N];
int lpos[N];
int rpos[N];
int depth[N];
void dfs(int u,int p){
    parent[u]=p;
    lpos[u]=rpos[u]=et.size();
    et.push_back(u);
    for(int v:edges[u]){
        if(v==p) continue;
        depth[v]=depth[u]+1;
        dfs(v,u);
        rpos[u]=et.size();
        et.push_back(u);
    }
}



inline pii get(int ind,int t){
    return query(0,lpos[ind],t);
}
void update(int l,int r,int v){
    update(l,mp(v,1));
    update(r+1,mp(-v,-1));
}
void solve(){
    int n,m,q;
    cin >> n >> m >> q;
    vector<pii> tree;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin >> u >> v;
        u--,v--;
        tree.push_back(mp(u,v));
    }
    vector<pair<int,pii>> chp;
    for(int i=0;i<m;i++){
        int ind, val;
        cin >>ind >> val;
        ind--;
        chp.push_back(mp(val,tree[ind]));
    }
    for(auto [u,v]:tree){
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    depth[0]=0;
    dfs(0,-1);
    //for(int u:et) cout << u << " ";
    //cout << "\n";
    //for(int i=0;i<n;i++) cout << lpos[i] << " " << rpos[i] << "\n";
    //cout << "\n";
    init(2*n-1);
    sort(chp.begin(),chp.end());
    int sptb[2*n][ln];
    for(int i=0;i<2*n-1;i++) sptb[i][0]=et[i];
    for(int j=0;j<ln-1;j++){
        for(int i=0;i<2*n-1;i++){
            if(i+(1<<j)>=2*n-1){
                sptb[i][j+1]=sptb[i][j];
            }
            else{
                sptb[i][j+1]=min(mp(depth[sptb[i][j]],sptb[i][j]),mp(depth[sptb[i+(1<<j)][j]],sptb[i+(1<<j)][j])).se;
            }
        }
    }
    auto lca=[&](int u,int v){
        int l=min(lpos[u],lpos[v]);
        int r=max(lpos[u],lpos[v])+1;
        int sz=pow2[r-l];
        int o1=sptb[l][sz];
        int o2=sptb[r-(1<<sz)][sz];
        return min(mp(depth[o1],o1),mp(depth[o2],o2)).se;
    };
    for(int i=0;i<m;i++){
        int w=chp[i].fi;
        auto [v,u]=chp[i].se;
        if(v==parent[u]) swap(v,u);
        //cout << lpos[v] << " "  << rpos[v] << " " << w << "!!\n";
        update(lpos[v],rpos[v],w);
    }
    int tt=node.size()-1;
    while(q--){
        int u,v,x,y;
        cin >> u >> v >> x >> y;
        u--,v--;
        int w=lca(u,v);
        int l=0;
        int r=tt/2;
        while(l<r){
            int mid=(l+r+1)/2;
            assert(2*mid<=tt);
            auto [val,cnt]=get(u,2*mid)+get(v,2*mid)-get(w,2*mid)-get(w,2*mid);
            if(val<=y){
                l=mid;
            } else r=mid-1;
        }
        int g=(get(u,tt)+get(v,tt)-get(w,tt)-get(w,tt)).se-(get(u,2*l)+get(v,2*l)-get(w,2*l)-get(w,2*l)).se;
        cout << max(x-g,-1LL) << "\n";
    }
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    //cin >> t;
    pow2[1]=0;
    for(int i=2;i<N;i++){
        if(i==(1<<(pow2[i-1]+1))) pow2[i]=pow2[i-1]+1;
        else pow2[i]=pow2[i-1];
    }
    t=1;
    while(t--) solve();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

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