Submission #958352

#	Time	Username	Problem	Language	Result	Execution time	Memory
958352		shenfe1	Food Court (JOI21_foodcourt)	C++17	100 / 100	679 ms	117272 KiB

foodcourt

#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=1e18;  
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
      |            ^~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11