Submission #970908

#TimeUsernameProblemLanguageResultExecution timeMemory
970908happy_nodeTwo Currencies (JOI23_currencies)C++17
30 / 100
289 ms26872 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MX=1e5+5; int N,M,Q; vector<int> qry[MX]; ll S[MX], T[MX], X[MX], Y[MX], ans[MX]; int L[MX], R[MX]; struct fenwick { ll t[MX]; void upd(int p, ll v) { for(int i=p;i<=N;i+=i&-i) t[i]+=v; } ll que(int p) { ll res=0; for(int i=p;i>0;i-=i&-i) res+=t[i]; return res; } ll que(int l, int r) { return que(r)-que(l-1); } void reset() { for(int i=0;i<MX;i++) t[i]=0; } } ft, tt; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin>>N>>M>>Q; for(int i=0;i<N-1;i++) { int u,v; cin>>u>>v; } vector<pair<int,int>> e; e.push_back({0,0}); for(int i=0;i<M;i++) { int p,c; cin>>p>>c; e.push_back({c,p}); } sort(e.begin(),e.end()); for(int i=0;i<Q;i++) { cin>>S[i]>>T[i]>>X[i]>>Y[i]; if(S[i]>T[i]) swap(S[i],T[i]); L[i]=0,R[i]=M; int m=(L[i]+R[i])/2; qry[m].push_back(i); } for(int ii=0;ii<20;ii++) { ft.reset(); tt.reset(); // activate for(int i=1;i<=M;i++) { auto [c,p]=e[i]; ft.upd(p,1); } vector<pair<int,int>> nxt; for(int i=0;i<=M;i++) { auto [c,p]=e[i]; if(i>0) { ft.upd(p,-1); tt.upd(p,c); } for(auto id:qry[i]) { ll s=tt.que(S[id],T[id]-1); if(s<=Y[id]) { ans[id]=ft.que(S[id],T[id]-1); L[id]=i+1; if(L[id]<=R[id]) nxt.push_back({(L[id]+R[id])/2, id}); } else { R[id]=i-1; if(L[id]<=R[id]) nxt.push_back({(L[id]+R[id])/2, id}); } } } for(int i=0;i<=M;i++) qry[i].clear(); for(auto [i,id]:nxt) qry[i].push_back(id); } for(int i=0;i<Q;i++) { if(ans[i]>X[i]) { cout<<-1<<'\n'; } else { cout<<X[i]-ans[i]<<'\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...