Submission #553086

#	Time	Username	Problem	Language	Result	Execution time	Memory
553086		BJoozz	Food Court (JOI21_foodcourt)	C++14	100 / 100	472 ms	46260 KiB

foodcourt

#define X first
#define Y second
#define pb push_back

#include<bits/stdc++.h>
using namespace std;
#define int long long
void maxx(int &a,int b){if(b>a) a=b;}
using ll = long long;
void minn(ll &a,ll b){if(b<a) a=b;}
//int down(const int &id){return id^1;}
//int upd(const int &id){return id;}
const int MAX=250000+4,mod=1e9+7;
const ll inf=1e15+3;
using ii =pair < int , int >;
vector < int > pr[MAX];
vector < ii >ad[MAX];
int C[MAX],K[MAX];
int SS[MAX*4],lz[MAX*4];
int ST[MAX*4];
int nx,val,n,m,Q,res;
void upd(int id,int l,int r){
    if(l==r){
        SS[id]+=val;lz[id]+=val;
        if(C[l])ST[id]+=val;
        return;
    }
    int mid=l+r>>1;
    if(lz[id]){
        lz[id<<1]+=lz[id];lz[id<<1|1]+=lz[id];
        SS[id<<1]+=lz[id];SS[id<<1|1]+=lz[id];
        lz[id]=0;
    }
    if(nx<=mid){
        SS[id<<1|1]+=val;lz[id<<1|1]+=val;
        upd(id<<1,l,mid);
    }
    else upd(id<<1|1,mid+1,r);
    ST[id]=ST[id<<1]+ST[id<<1|1];
    SS[id]=min(SS[id<<1],SS[id<<1|1]);
}
void get(int id,int l,int r){
    if(l==r){
        //cout<<"here "<<nx<<' '<<id<<' '<<l<<' '<<r<<' '<<SS[id]<<'\n';
        val=SS[id];return;
    }
    int mid=l+r>>1;
    if(lz[id]){
        lz[id<<1]+=lz[id];lz[id<<1|1]+=lz[id];
        SS[id<<1]+=lz[id];SS[id<<1|1]+=lz[id];
        lz[id]=0;
    }
    if(nx<=mid)get(id<<1,l,mid);
    else{
        minn(res,SS[id<<1]);
        get(id<<1|1,mid+1,r);
    }
    //SS[id]=min(SS[id<<1],SS[id<<1|1]);
}
void leo(int id,int l,int r){
    if(r<=nx){
        if(val>=ST[id]) {val-=ST[id];return;}
        if(l==r) {res=l;return;}
        int mid=l+r>>1;
        if(ST[id<<1|1]<=val) {
            val-=ST[id<<1|1];leo(id<<1,l,mid);
        }
        else leo(id<<1|1,mid+1,r);
        return;
    }
    int mid=l+r>>1;
    if(nx<=mid)leo(id<<1,l,mid);
    else{
        leo(id<<1|1,mid+1,r);
        if(!res) leo(id<<1,l,mid);
    }
    //SS[id]=min(SS[id<<1],SS[id<<1|1]);
}
void upd(int x){
    nx=x;val=K[x];//cout<<"upd "<<x<<' '<<K[x]<<'\n';
    K[x]=-K[x];
    upd(1,1,Q);
}

int get(int x,int lim){
    //cout<<x<<' '<<lim<<'\n';
    nx=x;res=0;
    get(1,1,Q);
    //cout<<val<<' '<<res<<'\n';
    if(val-res<lim) return 0;
    val=val-res-lim;res=0;
    leo(1,1,Q);
    //cout<<x<<' '<<lim<<' '<<res<<'\n';
    return C[res];
}
int ans[MAX];
signed main(){
    ///g++ grader.cpp .cpp -std=c++14 -O2 -Wl,--stack,10485760
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("JOI21_foodcourt.inp","r",stdin);//freopen("JOI21_foodcourt.out","w",stdout);
    cin>>n>>m>>Q;
    for(int i=1,t,x,y;i<=Q;i++){
        cin>>t>>x>>y;
        if(t==3)ad[x].pb(ii(i,y));
        else{
            ans[i]=-1;
            if(t==1){
                cin>>C[i]>>K[i];
                pr[x].pb(i);
                pr[y+1].pb(i);
            }
            else{
                cin>>K[i];K[i]=-K[i];
                pr[x].pb(i);
                pr[y+1].pb(i);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int u:pr[i])
            upd(u);
        for(ii u:ad[i]){
            ans[u.X]=get(u.X,u.Y);
        }
    }
    for(int i=1;i<=Q;i++) if(ans[i]!=-1)cout<<ans[i]<<'\n';

}

Compilation message (stderr)

foodcourt.cpp: In function 'void upd(long long int, long long int, long long int)':
foodcourt.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid=l+r>>1;
      |             ~^~
foodcourt.cpp: In function 'void get(long long int, long long int, long long int)':
foodcourt.cpp:48:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid=l+r>>1;
      |             ~^~
foodcourt.cpp: In function 'void leo(long long int, long long int, long long int)':
foodcourt.cpp:65:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid=l+r>>1;
      |                 ~^~
foodcourt.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int mid=l+r>>1;
      |             ~^~

• 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