Submission #1238970

#TimeUsernameProblemLanguageResultExecution timeMemory
1238970hamanp87Food Court (JOI21_foodcourt)C++17
24 / 100
495 ms78880 KiB
#include<bits/stdc++.h> using namespace std; using ll=long long; //#pragma GCC optimize("03,unroll-loops") //#pragma GCC target("avx2") //#pragma GCC target("sse4") #define all(v) v.begin(),v.end() #define F first #define S second #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front //#define randi uniform_int_distribution<long long> #define damoon(v) v.resize(unique(all(v))-v.begin()) //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //randi dist(0,10000000000000000); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<int,bool> pib; typedef pair<long long,bool> plb; typedef pair<int,pii> pip; typedef pair<pii,int> ppi; typedef vector<int> veci; typedef vector<long long> vecl; typedef vector<bool> vecb; typedef vector<pii> vecp; typedef set<int> seti; typedef set<long long> setl; typedef set<pii> setp; typedef map<int,int> mapii; typedef map<long long,long long> mapll; typedef map<int,bool> mapib; typedef map<long long,bool> maplb; const int inf=1e9,mod=1e9+7,neginf=-1e9,N=25e4+5,LG=20; const double PI=acos(-1); struct Node { ll mn,ind,lz; }; struct Segment { vector<Node> t; Segment(ll n) { t.resize(4*n); } void push(ll id,ll L,ll R) { if(!t[id].lz) return; ll v=t[id].lz; t[id].lz=0; t[id].mn+=v; if(L==R) return; t[2*id+0].lz+=v; t[2*id+1].lz+=v; } Node Merge(Node a,Node b) { if(a.ind==-1) return b; if(b.ind==-1) return a; Node ret; ret.lz=0; ret.ind=(a.mn<=b.mn?a.ind:b.ind); ret.mn=min(a.mn,b.mn); return ret; } void initialize(ll id,ll L,ll R) { if(L==R) { t[id].ind=L; t[id].lz=0; t[id].mn=0; return; } ll mid=(L+R)>>1; initialize(2*id+0,L,mid+0); initialize(2*id+1,mid+1,R); t[id]=Merge(t[2*id+0],t[2*id+1]); } void update(ll id,ll L,ll R,ll l,ll r,ll v) { push(id,L,R); if(R<l or L>r) return; if(l<=L and R<=r) { t[id].lz+=v; push(id,L,R); return; } ll mid=(L+R)>>1; update(2*id+0,L,mid+0,l,r,v); update(2*id+1,mid+1,R,l,r,v); t[id]=Merge(t[2*id+0],t[2*id+1]); } Node get(ll id,ll L,ll R,ll l,ll r) { push(id,L,R); if(R<l or L>r) return {LLONG_MAX,-1,0}; if(L>=l and R<=r) return t[id]; ll mid=(L+R)>>1; return Merge(get(2*id+0,L,mid,l,r),get(2*id+1,mid+1,R,l,r)); } }; struct Fenwick { vector<vecl> f; Fenwick(ll n) { f.resize(n,vecl(2,0)); } void add(ll i,ll v,ll t) { for(;i<N;i+=i&-i) f[i][t]+=v; } ll get(ll i,ll t,ll s=0) { for(;i;i-=i&-i) s+=f[i][t]; return s; } ll BS(ll k,ll p=0) { for(ll b=LG-1;b>=0;b--) { if(p+(1<<b)>=N) continue; if(f[p+(1<<b)][0]<k) { k-=f[p+(1<<b)][0]; p+=(1<<b); } } return p+1; } }; void solve() { ll n,m,q; cin>>n>>m>>q; Segment Seg(q); Seg.initialize(1,0,q); Fenwick Fen(N); vector<vecl> opn(N),cls(N),sor(N),ops(q+1,vecl(4,-1)); ll cnt=0; for(ll i=1;i<=q;i++) { ll t; cin>>t; if(t==1) { ll l,r,id,k; cin>>l>>r>>id>>k; ops[i]={l,r,k,id}; opn[l].pub(i); cls[r+1].pub(i); } else if(t==2) { ll l,r,k; cin>>l>>r>>k; ops[i]={l,r,k,-1}; opn[l].pub(i); cls[r+1].pub(i); } else { ll a,k; cin>>a>>k; ops[i]={-1,cnt++,a,k}; sor[a].pub(i); } } vecl ans(cnt,-1); for(ll i=1;i<=n;i++) { for(ll ind:opn[i]) { if(ops[ind][3]==-1) { Seg.update(1,0,q,ind,q,-ops[ind][2]); Fen.add(ind,ops[ind][2],1); } else { Seg.update(1,0,q,ind,q,ops[ind][2]); Fen.add(ind,ops[ind][2],0); } } for(ll ind:cls[i]) { if(ops[ind][3]==-1) { Seg.update(1,0,q,ind,q,ops[ind][2]); Fen.add(ind,-ops[ind][2],1); } else { Seg.update(1,0,q,ind,q,-ops[ind][2]); Fen.add(ind,-ops[ind][2],0); } } for(ll ind:sor[i]) { Node X=Seg.get(1,0,q,0,ind); if(X.mn>=0) X.ind=0; int xd=Fen.get(X.ind,0); xd+=Fen.get(ind,1)-Fen.get(X.ind,1); xd+=ops[ind][3]; if(xd>Fen.get(ind,0) or Fen.get(ind,0)==0) { ans[ops[ind][1]]=0; continue; } int tmp=Fen.BS(xd); if(ops[tmp][3]==-1 or ops[tmp][0]==-1 or tmp>q or Fen.get(tmp,0)<xd) { ans[ops[ind][1]]=0; } else { ans[ops[ind][1]]=ops[tmp][3]; } } } for(ll i=0;i<cnt;i++) cout<<ans[i]<<"\n"; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); //ifstream fin("in.txt"); //ofstream fout("out.txt"); int t=1; //cin>>t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...