Submission #976846

#TimeUsernameProblemLanguageResultExecution timeMemory
976846modwweFood Court (JOI21_foodcourt)C++17
100 / 100
343 ms56916 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2") #include<bits/stdc++.h> #define int long long //#define ll long long #define down cout<<'\n'; #define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); #define modwwe int t;cin>>t; while(t--) #define bit(i,j) (i>>j&1) #define sobit(a) __builtin_popcountll(a) #define task "test" #define fin(x) freopen(x".inp","r",stdin) #define fou(x) freopen(x".out","w",stdout) #define pb push_back #define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; using namespace std; void ngha(); const int mod2=1e9+7; const int mod1=998244353; struct ib { int a; int b; }; struct icd { int a,b; }; struct ic { int a,b,c; }; struct id { int a,b,c,d; }; struct ie { int a,b,c, d,e; }; int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l; int i,s10,s12; int el=29; main() { //#ifndef ONLINE_JUDGE // fin(task),fou(task); //#endif NHP //modwwe // cin>>res; ngha(); } int c[250001]; ic t[1000001]; id b[250001]; void ff(int x) { for(int i=x*2;i<=x*2+1;i++) { if(t[i].a>=t[x].b)t[i].a-=t[x].b; else t[i].b+=t[x].b-t[i].a,t[i].a=0; t[i].a+=t[x].a; t[i].c+=t[x].c; } t[x].a=t[x].b=t[x].c=0; } void upd(int node,int l,int r,int l1,int r1,int k,int z) { if(l>r1||r<l1) return; if(l>=l1&&r<=r1) { if(k==1) t[node].a+=z,t[node].c+=z; if(k==0) { if(t[node].a>=z)t[node].a-=z; else t[node].b+=z-t[node].a,t[node].a=0; } return; } ff(node); int mid=l+r>>1; upd(node<<1,l,mid,l1,r1,k,z); upd(node<<1|1,mid+1,r,l1,r1,k,z); } int get(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return 0; if(l>=l1&&r<=r1) return t[node].a; int mid=l+r>>1; ff(node); return get(node<<1,l,mid,l1,r1)+get(node<<1|1,mid+1,r,l1,r1); } int get2(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return 0; if(l>=l1&&r<=r1) return t[node].c; int mid=l+r>>1; ff(node); return get2(node<<1,l,mid,l1,r1)+get2(node<<1|1,mid+1,r,l1,r1); } int bit[250001]; void upd(int x,int y) { for(x;x<=k;x+=x&-x) bit[x]+=y; } int get(int x) { int ss=0; for(x;x;x-=x&-x) ss+=bit[x]; return ss; } vector<ib> v[250001]; vector<ib> v2[250002]; vector<ib> v3[250002]; void ngha() { cin>>n>>m>>k; for(int i=1;i<=k;i++) { cin>>l; if(l==3){cin>>l>>r; c[++dem]=0; s2=get2(1,1,n,l,l); s3=get(1,1,n,l,l); //cout<<s3 ,down ///cout<<s2-s3+r<<" "<<l<<" "<<r<<" "<<s3,down /// if(i==90) cout<<r<<" "<<s3<<" cucucuc",down if(r<=s3) { ///cout<<s2-s3+r<<" "<<s3,down /// cout<<i<<" cucu "<<dem,down v[l].pb({s2-s3+r,dem}); } } else if(l==2) { cin>>l>>r>>s3; upd(1,1,n,l,r,0,s3); } else if(l==1) { cin>>l>>r>>s2>>s3; b[++dem2]={l,r,s2,s3}; upd(1,1,n,l,r,1,s3); ///if(i==1) /// cout<<get(1,1,n,3,3),down } } for(int i=1;i<=dem2;i++) { v2[b[i].a].pb({b[i].d,i}); v3[b[i].b+1].pb({b[i].d,i}); } for(int i=1;i<=n;i++) { for(auto x:v2[i]) { upd(x.b,x.a); } for(auto x:v3[i]) { upd(x.b,-x.a); } for(auto x:v[i]) { l=1; r=k; while(l<=r) { int mid=l+r>>1; if(get(mid)>=x.a)r=mid-1; else l=mid+1; } /// cout<<r+1<<" "<<dem2<<" "<<get(3),down c[x.b]=b[r+1].c; } } for(int i=1;i<=dem;i++) cout<<c[i],down }

Compilation message (stderr)

foodcourt.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main()
      | ^~~~
foodcourt.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:84:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |      int mid=l+r>>1;
      |              ~^~
foodcourt.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:92:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |         int mid=l+r>>1;
      |                 ~^~
foodcourt.cpp: In function 'long long int get2(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:100:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |        int mid=l+r>>1;
      |                ~^~
foodcourt.cpp: In function 'void upd(long long int, long long int)':
foodcourt.cpp:107:10: warning: statement has no effect [-Wunused-value]
  107 |      for(x;x<=k;x+=x&-x)
      |          ^
foodcourt.cpp: In function 'long long int get(long long int)':
foodcourt.cpp:112:11: warning: statement has no effect [-Wunused-value]
  112 |       for(x;x;x-=x&-x)
      |           ^
foodcourt.cpp: In function 'void ngha()':
foodcourt.cpp:175:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  175 |                    int mid=l+r>>1;
      |                            ~^~
#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...