oj.uz

Submission #553061

# Submission time Handle Problem Language Result Execution time Memory
553061 2022-04-24T14:35:08 Z BJoozz Food Court (JOI21_foodcourt) C++14
34 / 100
 415 ms 41240 KB 
#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);
}

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=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);
        }
    }
    for(int i=1;i<=Q;i++) if(ans[i]!=-1)cout<<ans[i]<<'\n';

}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 17888 KB Output is correct
2 Correct 72 ms 17976 KB Output is correct
3 Correct 61 ms 17968 KB Output is correct
4 Correct 60 ms 17968 KB Output is correct
5 Correct 74 ms 17960 KB Output is correct
6 Correct 87 ms 17996 KB Output is correct
7 Correct 31 ms 16964 KB Output is correct
8 Correct 40 ms 16912 KB Output is correct
9 Correct 63 ms 17692 KB Output is correct
10 Correct 66 ms 17872 KB Output is correct
11 Correct 64 ms 17836 KB Output is correct
12 Correct 68 ms 17948 KB Output is correct
13 Incorrect 60 ms 17428 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 33968 KB Output is correct
2 Correct 264 ms 31436 KB Output is correct
3 Correct 370 ms 35148 KB Output is correct
4 Correct 258 ms 31540 KB Output is correct
5 Correct 274 ms 31164 KB Output is correct
6 Correct 391 ms 41240 KB Output is correct
7 Correct 140 ms 34608 KB Output is correct
8 Correct 131 ms 34712 KB Output is correct
9 Correct 383 ms 41128 KB Output is correct
10 Correct 353 ms 41200 KB Output is correct
11 Correct 355 ms 40236 KB Output is correct
12 Correct 415 ms 41136 KB Output is correct
13 Correct 377 ms 40136 KB Output is correct
14 Correct 364 ms 41060 KB Output is correct
15 Correct 362 ms 40996 KB Output is correct
16 Correct 360 ms 41084 KB Output is correct
17 Correct 349 ms 40868 KB Output is correct
18 Correct 368 ms 40656 KB Output is correct
19 Correct 363 ms 41064 KB Output is correct
20 Correct 355 ms 40528 KB Output is correct
21 Correct 350 ms 41080 KB Output is correct
22 Correct 357 ms 40980 KB Output is correct
23 Correct 366 ms 41116 KB Output is correct
24 Correct 371 ms 40908 KB Output is correct
25 Correct 270 ms 38552 KB Output is correct
26 Correct 281 ms 38980 KB Output is correct
27 Correct 276 ms 40220 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 17688 KB Output is correct
2 Correct 73 ms 17964 KB Output is correct
3 Correct 69 ms 18028 KB Output is correct
4 Correct 49 ms 18088 KB Output is correct
5 Correct 60 ms 18988 KB Output is correct
6 Correct 76 ms 19692 KB Output is correct
7 Correct 36 ms 17920 KB Output is correct
8 Correct 35 ms 17696 KB Output is correct
9 Correct 49 ms 18724 KB Output is correct
10 Correct 43 ms 17516 KB Output is correct
11 Correct 62 ms 19036 KB Output is correct
12 Correct 61 ms 19024 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12264 KB Output isn't correct
2 Halted 0 ms 0 KB -