Submission #386398

#TimeUsernameProblemLanguageResultExecution timeMemory
386398haojiandanFood Court (JOI21_foodcourt)C++14
89 / 100
1004 ms50400 KiB
#include <bits/stdc++.h> using namespace std; template <typename T> void read(T &t) { t=0; char ch=getchar(); int f=1; while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f; } typedef long long ll; const int maxn=250010; int n,m,q; ll mn[maxn*4],mx[maxn*4],lazy[maxn*4]; int tim[maxn*4],T[maxn*4]; struct node { int op,l,r,c; ll k; } Q[maxn]; int tot,tot2,zero[maxn*4]; ll all[maxn]; struct Node { int l,r,id; } st[maxn],st2[maxn]; int pos[maxn],res[maxn],now; void puttag(int root,ll delta) { lazy[root]+=delta,mn[root]+=delta,mx[root]+=delta; mn[root]=max(mn[root],0LL),mx[root]=max(mx[root],0LL); } void pushdown(int root) { if (zero[root]) { zero[root<<1]=zero[root<<1|1]=1; zero[root]=0; mx[root<<1]=mn[root<<1]=mx[root<<1|1]=mn[root<<1|1]=0; lazy[root<<1]=lazy[root<<1|1]=0; } if (lazy[root]) { puttag(root<<1,lazy[root]); puttag(root<<1|1,lazy[root]); lazy[root]=0; } if (T[root]) { tim[root<<1]=max(tim[root<<1],T[root]); T[root<<1]=max(T[root<<1],T[root]); tim[root<<1|1]=max(tim[root<<1|1],T[root]); T[root<<1|1]=max(T[root<<1|1],T[root]); T[root]=0; } } void pushup(int root) { mn[root]=min(mn[root<<1],mn[root<<1|1]); mx[root]=max(mx[root<<1],mx[root<<1|1]); } void add(int L,int R,int l,int r,int root,ll delta,int flag) { if (L<=l&&r<=R) { if (!flag) { puttag(root,delta); } if (mn[root]==0) { if (mx[root]==0) { tim[root]=T[root]=now; lazy[root]=0; zero[root]=1; } else { int mid=(l+r)>>1; pushdown(root); add(L,R,l,mid,root<<1,delta,1); add(L,R,mid+1,r,root<<1|1,delta,1); } } return; } pushdown(root); int mid=(l+r)>>1; if (L<=mid) add(L,R,l,mid,root<<1,delta,flag); if (mid<R) add(L,R,mid+1,r,root<<1|1,delta,flag); pushup(root); } int query(int x,int l,int r,int root) { if (l==r) return tim[root]; int mid=(l+r)>>1; pushdown(root); if (x<=mid) return query(x,l,mid,root<<1); return query(x,mid+1,r,root<<1|1); } namespace BIT { ll tr[maxn]; void add(int x,ll delta) { for (;x<=n;x+=x&(-x)) tr[x]+=delta; } ll query(int x) { ll res=0; for (;x;x-=x&(-x)) res+=tr[x]; return res; } void add(int l,int r,ll delta) { add(l,delta),add(r+1,-delta); } void clear() { for (int i=1;i<=n;i++) tr[i]=0; } }; namespace Seg { ll add[maxn*4],tr[maxn*4],mx[maxn*4]; bool bz[maxn*4]; void mark(int root,int op,ll delta) { if (op==1) add[root]+=delta,tr[root]+=delta; else { tr[root]=max(tr[root],delta); delta-=add[root]; if (bz[root]) mx[root]=max(mx[root],delta); else bz[root]=1,mx[root]=delta; } } void pushdown(int root) { if (bz[root]) { mark(root<<1,0,mx[root]); mark(root<<1|1,0,mx[root]); mx[root]=bz[root]=0; } if (add[root]) { mark(root<<1,1,add[root]); mark(root<<1|1,1,add[root]); add[root]=0; } } void addd(int L,int R,int l,int r,int root,int op,ll delta) { if (L<=l&&r<=R) { mark(root,op,delta); return; } pushdown(root); int mid=(l+r)>>1; if (L<=mid) addd(L,R,l,mid,root<<1,op,delta); if (mid<R) addd(L,R,mid+1,r,root<<1|1,op,delta); tr[root]=max(tr[root<<1],tr[root<<1|1]); } ll query(int x,int l,int r,int root) { if (l==r) return tr[root]; int mid=(l+r)>>1; pushdown(root); if (x<=mid) return query(x,l,mid,root<<1); return query(x,mid+1,r,root<<1|1); } }; vector<pair<int,int> > g[maxn]; ll buc[maxn],haha[maxn]; int main() { //freopen("1.txt","r",stdin); read(n),read(m),read(q); int op,l,r,c,mid; ll tmp,k; if (m==1) { for (int i=1;i<=q;i++) { now=i; read(op); if (op==1) { read(l),read(r),read(c),read(k); Seg::addd(l,r,1,n,1,1,k); } else if (op==2) { read(l),read(r),read(k); c=0; Seg::addd(l,r,1,n,1,1,-k); Seg::addd(1,n,1,n,1,2,0); } else { read(c),read(k); l=r=0; tmp=Seg::query(c,1,n,1); if (tmp>=k) puts("1"); else puts("0"); } } exit(0); } for (int i=1;i<=q;i++) { now=i; read(op); if (op==1) { read(l),read(r),read(c),read(k); add(l,r,1,n,1,k,0); } else if (op==2) { read(l),read(r),read(k); c=0; add(l,r,1,n,1,-k,0); } else { read(c),read(k); l=r=0; pos[i]=query(c,1,n,1); // printf("%d\n",pos[i]); } Q[i]=(node){op,l,r,c,k}; } //puts(""); for (int i=1;i<=q;i++) if (Q[i].op==3) { st[++tot]=(Node){pos[i]+1,i,i}; l=pos[i]+1,r=i; if (l>1) g[l-1].push_back(make_pair(i,-1)); g[r].push_back(make_pair(i,1)); } for (int i=1;i<=q;i++) { if (Q[i].op==2) BIT::add(Q[i].l,Q[i].r,Q[i].k); for (pair<int,int> A : g[i]) { all[A.first]+=BIT::query(Q[A.first].c)*A.second; } } BIT::clear(); for (int i=1;i<=q;i++) g[i].clear(); for (int i=1;i<=q;i++) if (Q[i].op==3) { g[pos[i]].push_back(make_pair(i,0)); } for (int i=1;i<=q;i++) { if (Q[i].op==1) BIT::add(Q[i].l,Q[i].r,Q[i].k); for (pair<int,int> A : g[i]) { haha[A.first]+=BIT::query(Q[A.first].c); } } //for (int i=1;i<=q;i++) if (Q[i].op==3) printf(" %lld %lld\n",all[i],haha[i]); while (tot) { now=0; for (int i=1;i<=q;i++) g[i].clear(); BIT::clear(); for (int i=1;i<=tot;i++) { l=st[i].l,r=st[i].r,mid=(l+r)>>1; //if (pos[st[i].id]>0) g[pos[st[i].id]].push_back(make_pair(i,-1)); g[mid].push_back(make_pair(i,1)); buc[i]=0; } for (int i=1;i<=q;i++) { if (Q[i].op==1) BIT::add(Q[i].l,Q[i].r,Q[i].k); for (pair<int,int> A : g[i]) { buc[A.first]+=BIT::query(Q[st[A.first].id].c)*A.second; } } for (int i=1;i<=tot;i++) { l=st[i].l,r=st[i].r,mid=(l+r)>>1; //printf("%d %d %d %d %lld\n",st[i].id,l,r,mid,buc[i]); if (buc[i]-haha[st[i].id]-all[st[i].id]>=Q[st[i].id].k) res[st[i].id]=mid,r=mid-1; else l=mid+1; if (l<=r) st2[++tot2]=(Node){l,r,st[i].id}; } tot=tot2; tot2=0; for (int i=1;i<=tot;i++) st[i]=st2[i]; } for (int i=1;i<=q;i++) if (Q[i].op==3) printf("%d\n",Q[res[i]].c); return 0; } /* 0. Enough array size? Enough array size? Enough array size? Integer overflow? 1. Think TWICE, Code ONCE! Are there any counterexamples to your algo? 2. Be careful about the BOUNDARIES! N=1? P=1? Something about 0? 3. Do not make STUPID MISTAKES! Time complexity? Memory usage? Precision error? */
#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...