Submission #553059

#	Time	Username	Problem	Language	Result	Execution time	Memory
553059		BJoozz	Food Court (JOI21_foodcourt)	C++17	0 / 100	365 ms	41028 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 nx,val,n,m,Q,res;
void upd(int id,int l,int r){
    if(nx<=l){
        //cout<<"add1z1z "<<id<<' '<<l<<' '<<r<<' '<<val<<'\n';
        SS[id]+=val;lz[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)upd(id<<1,l,mid);
    upd(id<<1|1,mid+1,r);
    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(SS[id]>=val) return;
        if(l==r) {res=l;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(SS[id<<1|1]>=val) leo(id<<1,l,mid);
        else leo(id<<1|1,mid+1,r);
        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)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);
}
void get2(int x){
    nx=x;
    get(1,1,n);//cout<<val<<'\n';
}
int get(int x,int lim){
    //cout<<x<<' '<<lim<<'\n';
    nx=x;res=inf;
    get(1,1,Q);
    //cout<<val<<' '<<res<<'\n';
    if(val-res<lim) return 0;
    val=res+lim;res=0;
    leo(1,1,Q);
    return C[res+1];
}
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);
            //return 0;
            //leo()
            ///continue bae
        }
    }
    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:28:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int mid=l+r>>1;
      |             ~^~
foodcourt.cpp: In function 'void get(long long int, long long int, long long int)':
foodcourt.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid=l+r>>1;
      |             ~^~
foodcourt.cpp: In function 'void leo(long long int, long long int, long long int)':
foodcourt.cpp:60:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int mid=l+r>>1;
      |                 ~^~
foodcourt.cpp:70:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int mid=l+r>>1;
      |             ~^~

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