Submission #958350

#TimeUsernameProblemLanguageResultExecution timeMemory
958350shenfe1Food Court (JOI21_foodcourt)C++17
24 / 100
606 ms222736 KiB
#include <bits/stdc++.h> #pragma optimize("Ofast") #pragma target("avx2") #pragma optimize("unroll-loops") using namespace std; #define ll long long #define ld long double #define pb push_back #define pf push_front #define pii pair<int,int> #define all(v) v.begin(),v.end() #define F first #define S second #define mem(a,i) memset(a,i,sizeof(a)) #define sz(s) (int)s.size() #define y1 yy #define ppb pop_back #define lb lower_bound #define ub upper_bound #define gcd(a,b) __gcd(a,b) #define in insert #define int ll #define ull unsigned ll const int MAX=3e5+10; const int B=331; const int maxB=1000; const int N=104; const int block=450; const int inf=1e9; const int mod=1e9+7; const int mod1=1e9+9; const ld eps=1e-9; int dx[8]={1,0,-1,0,1,-1,-1,1}; int dy[8]={0,1,0,-1,1,-1,1,-1}; int binpow(int a,int n){ if(!n)return 1; if(n%2==1)return a*binpow(a,n-1)%mod; int k=binpow(a,n/2); return k*k%mod; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct segtree{ int t[3][4*MAX],op[3][4*MAX]; void init(){ mem(t,0); mem(op,0); } void upd(int v,int o,int x){ if(op[2][v]==o){ t[2][v]+=x; return; } if(op[2][v]==1){ if(t[2][v]>=x){ t[2][v]-=x; } else{ op[2][v]=(op[2][v]^1); t[2][v]=x-t[2][v]; } return; } if(op[1][v]==op[2][v]){ t[1][v]+=t[2][v]; } else{ if(t[1][v]>=t[2][v]){ t[1][v]-=t[2][v]; } else{ op[1][v]=(op[1][v]^1); t[1][v]=t[2][v]-t[1][v]; } } t[2][v]=x; op[2][v]=o; } void push(int v){ for(int i=1;i<=2;i++){ upd(2*v,op[i][v],t[i][v]); upd(2*v+1,op[i][v],t[i][v]); op[i][v]=t[i][v]=0; } } void update(int v,int tl,int tr,int l,int r,int o,int x){ if(l>r||tl>r||l>tr)return; if(l<=tl&&tr<=r){ upd(v,o,x); return; } push(v); int tm=(tl+tr)/2; update(2*v,tl,tm,l,r,o,x); update(2*v+1,tm+1,tr,l,r,o,x); } int get(int v,int tl,int tr,int pos){ if(tl==tr){ int ans=0; for(int i=1;i<=2;i++){ if(op[i][v]==0)ans-=t[i][v]; else ans+=t[i][v]; ans=max(ans,0ll); } return ans; } push(v); int tm=(tl+tr)/2; if(pos<=tm)return get(2*v,tl,tm,pos); else return get(2*v+1,tm+1,tr,pos); } }t; int n,m,q; int del[MAX]; int type[MAX]; int l[MAX],r[MAX],c[MAX],x[MAX]; vector<pii> zap[MAX]; int ans[MAX]; struct segtree1{ pii t[4*MAX]; int add[4*MAX]; void build(int v,int tl,int tr){ if(tl==tr){ t[v].S=tl; return; } int tm=(tl+tr)/2; build(2*v,tl,tm); build(2*v+1,tm+1,tr); t[v]=max(t[2*v],t[2*v+1]); } void init(){ mem(t,0); mem(add,0); build(1,1,n); } void push(int v){ add[2*v]+=add[v]; add[2*v+1]+=add[v]; t[2*v].F+=add[v]; t[2*v+1].F+=add[v]; add[v]=0; } pii get(int v,int tl,int tr,int l,int r){ if(l>r||tl>r||l>tr)return {-inf,-inf}; if(l<=tl&&tr<=r)return t[v]; push(v); int tm=(tl+tr)/2; return max(get(2*v,tl,tm,l,r),get(2*v+1,tm+1,tr,l,r)); } void update(int v,int tl,int tr,int l,int r,int x){ if(l>r||tl>r||l>tr)return; if(l<=tl&&tr<=r){ t[v].F+=x; add[v]+=x; return; } push(v); int tm=(tl+tr)/2; update(2*v,tl,tm,l,r,x); update(2*v+1,tm+1,tr,l,r,x); t[v]=max(t[2*v],t[2*v+1]); } }t1; void solve(){ cin>>n>>m>>q; mem(ans,-1); t.init(); t1.init(); for(int i=1;i<=q;i++){ cin>>type[i]; if(type[i]==1){ cin>>l[i]>>r[i]>>c[i]>>x[i]; t1.update(1,1,n,l[i],r[i],x[i]); t.update(1,1,n,l[i],r[i],1,x[i]); } else if(type[i]==2){ cin>>l[i]>>r[i]>>x[i]; t.update(1,1,n,l[i],r[i],0,x[i]); } else{ cin>>l[i]>>r[i]; // cout<<i<<" "<<l[i]<<" "<<r[i]<<" "<<t1.get(1,1,n,l[i],l[i]).F<<" "<<t.get(1,1,n,l[i])<<"\n"; r[i]+=t1.get(1,1,n,l[i],l[i]).F-t.get(1,1,n,l[i]); zap[l[i]].pb({r[i],i}); // cout<<l[i]<<" "<<r[i]<<"\n"; } } t1.init(); for(int i=1;i<=n;i++){ sort(all(zap[i])); reverse(all(zap[i])); // cout<<i<<"\n"; // for(auto x:zap[i]){ // cout<<x.F<<" "<<x.S<<"\n"; // } if(!zap[i].empty())t1.update(1,1,n,i,i,-zap[i].back().F); else t1.update(1,1,n,i,i,-inf); } // for(int i=1;i<=n;i++){ // cout<<t1.get(1,1,n,i,i).F<<" "; // } // cout<<"\n"; for(int i=1;i<=q;i++){ if(type[i]==1){ t1.update(1,1,n,l[i],r[i],x[i]); } while(t1.get(1,1,n,1,n).F>=0){ int pos=t1.get(1,1,n,1,n).S; // cout<<pos<<" "<<i<<" "<<zap[pos].back().S<<" "<<t1.get(1,1,n,1,n).F<<"\n"; if(zap[pos].back().S>i)ans[zap[pos].back().S]=c[i]; else ans[zap[pos].back().S]=0; if(sz(zap[pos])>1){ t1.update(1,1,n,pos,pos,zap[pos].back().F-zap[pos][sz(zap[pos])-2].F); } else{ t1.update(1,1,n,pos,pos,-inf); } zap[pos].ppb(); } } for(int i=1;i<=n;i++){ while(!zap[i].empty()){ ans[zap[i].back().S]=0; zap[i].ppb(); } } for(int i=1;i<=q;i++){ if(ans[i]!=-1)cout<<ans[i]<<"\n"; } } signed main(){ // freopen("triangles.in","r",stdin); // freopen("triangles.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // prec(); int t=1; // cin>>t; while(t--)solve(); }

Compilation message (stderr)

foodcourt.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
foodcourt.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      | 
foodcourt.cpp:5: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    5 | #pragma optimize("unroll-loops")
      | 
foodcourt.cpp: In member function 'void segtree1::init()':
foodcourt.cpp:17:38: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   17 | #define mem(a,i) memset(a,i,sizeof(a))
      |                                      ^
foodcourt.cpp:149:5: note: in expansion of macro 'mem'
  149 |     mem(t,0);
      |     ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~
#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...