oj.uz

Submission #905241

# Submission time Handle Problem Language Result Execution time Memory
905241 2024-01-12T21:00:49 Z alexander707070 Food Court (JOI21_foodcourt) C++14
9 / 100
 1000 ms 112444 KB 
#include<bits/stdc++.h>
#define MAXN 500007
using namespace std;

struct event{
    int c,tim;
    long long k;
};

const long long inf=1e17;

int n,m,q,type,l,r,s,t;

long long minsz[4*MAXN],lazy[4*MAXN],maxsz[4*MAXN];
int c[MAXN];

vector< event > tree[4*MAXN];
vector<long long> pref[4*MAXN];

void update(int v,int l,int r,int ll,int rr,event news){
    if(ll>rr)return;
    if(l==ll and r==rr){
        tree[v].push_back(news);

        if(pref[v].empty())pref[v].push_back(news.k);
        else pref[v].push_back(pref[v].back()+news.k);

        return;
    }else{
        int tt=(l+r)/2;
        update(2*v,l,tt,ll,min(tt,rr),news);
        update(2*v+1,tt+1,r,max(tt+1,ll),rr,news);
    }
}

void psh(int v){
    minsz[2*v]+=lazy[v];
    maxsz[2*v]+=lazy[v];

    minsz[2*v]=max(minsz[2*v],0LL);
    maxsz[2*v]=max(maxsz[2*v],0LL);

    minsz[2*v+1]+=lazy[v];
    maxsz[2*v+1]+=lazy[v];

    minsz[2*v+1]=max(minsz[2*v+1],0LL);
    maxsz[2*v+1]=max(maxsz[2*v+1],0LL);

    lazy[2*v]+=lazy[v];
    lazy[2*v+1]+=lazy[v];

    lazy[v]=0;
}

void add(int v,int l,int r,int ll,int rr,long long val){
    if(ll>rr)return;
    if(l==ll and r==rr){
        minsz[v]+=val;
        maxsz[v]+=val;

        lazy[v]+=val;
    }else{
        psh(v);
        int tt=(l+r)/2;
        add(2*v,l,tt,ll,min(tt,rr),val);
        add(2*v+1,tt+1,r,max(tt+1,ll),rr,val);

        minsz[v]=min(minsz[2*v],minsz[2*v+1]);
        maxsz[v]=max(maxsz[2*v],maxsz[2*v+1]);
    }
}

void rem(int v,int l,int r,int ll,int rr,long long val){
    if(ll>rr)return;

    if(l==ll and r==rr and minsz[v]>=val){
        minsz[v]-=val;
        lazy[v]-=val;
        return;
    }

    if(l==ll and r==rr and maxsz[v]<val){
        minsz[v]=maxsz[v]=0;
        lazy[v]=-inf;
        return;
    }

    psh(v);
    int tt=(l+r)/2;
    rem(2*v,l,tt,ll,min(tt,rr),val);
    rem(2*v+1,tt+1,r,max(tt+1,ll),rr,val);

    minsz[v]=min(minsz[2*v],minsz[2*v+1]);
    maxsz[v]=max(maxsz[2*v],maxsz[2*v+1]);
}

long long getsz(int v,int l,int r,int pos){
    if(l==r)return minsz[v];

    psh(v);
    int tt=(l+r)/2;
    if(pos<=tt)return getsz(2*v,l,tt,pos);
    else getsz(2*v+1,tt+1,r,pos);
}

long long calc(int v,int qr){
    long long res=0;

    for(int i=tree[v].size()-1;i>=0 and tree[v][i].tim>=qr;i--){
        res+=tree[v][i].k;
    }
    return res;
}

long long howmany(int v,int l,int r,int pos,int qr){
    if(l==r){
        return calc(v,qr);
    }else{
        int tt=(l+r)/2;
        if(pos<=tt)return howmany(2*v,l,tt,pos,qr) + calc(v,qr);
        else return howmany(2*v+1,tt+1,r,pos,qr) + calc(v,qr);
    }
}

int bin(int s,long long t){
    int l=0,r=q+1,tt;
    while(l+1<r){
        tt=(l+r)/2;
        if(howmany(1,1,n,s,tt)>=t){
            l=tt;
        }else{
            r=tt;
        }
    }

    if(c[l]==0)cout<<1/0;
    return c[l];
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m>>q;
    
    for(int i=1;i<=q;i++){
        cin>>type;
        if(type==1){
            cin>>l>>r>>s>>t;
            c[i]=s;

            //add(1,1,n,l,r,t);
            for(int i=l;i<=r;i++){
                minsz[i]+=t;
            }

            update(1,1,n,l,r,{s,i,t});
        }else if(type==2){
            cin>>l>>r>>s;
            //rem(1,1,n,l,r,s);
            for(int i=l;i<=r;i++){
                minsz[i]=max(minsz[i]-s,0LL);
            }
        }else{
            cin>>s>>t;
            if(minsz[s]<t)cout<<"0\n";
            else cout<<bin(s,minsz[s]-t+1)<<"\n";
        }
    }

    return 0;
}

Compilation message

foodcourt.cpp: In function 'int bin(int, long long int)':
foodcourt.cpp:136:23: warning: division by zero [-Wdiv-by-zero]
  136 |     if(c[l]==0)cout<<1/0;
      |                      ~^~
foodcourt.cpp: In function 'long long int getsz(int, int, int, int)':
foodcourt.cpp:103:15: warning: control reaches end of non-void function [-Wreturn-type]
  103 |     else getsz(2*v+1,tt+1,r,pos);
      |          ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 97104 KB Output is correct
2 Correct 30 ms 97116 KB Output is correct
3 Correct 32 ms 97116 KB Output is correct
4 Correct 31 ms 97444 KB Output is correct
5 Correct 30 ms 97112 KB Output is correct
6 Correct 27 ms 95068 KB Output is correct
7 Correct 33 ms 97108 KB Output is correct
8 Correct 31 ms 97336 KB Output is correct
9 Correct 31 ms 97116 KB Output is correct
10 Correct 31 ms 97368 KB Output is correct
11 Correct 30 ms 95320 KB Output is correct
12 Correct 31 ms 97240 KB Output is correct
13 Correct 30 ms 96860 KB Output is correct
14 Correct 30 ms 95068 KB Output is correct
15 Correct 29 ms 97112 KB Output is correct
16 Correct 31 ms 97364 KB Output is correct
17 Correct 30 ms 97116 KB Output is correct
18 Correct 30 ms 95244 KB Output is correct
19 Correct 31 ms 97024 KB Output is correct
20 Correct 32 ms 97168 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 97104 KB Output is correct
2 Correct 30 ms 97116 KB Output is correct
3 Correct 32 ms 97116 KB Output is correct
4 Correct 31 ms 97444 KB Output is correct
5 Correct 30 ms 97112 KB Output is correct
6 Correct 27 ms 95068 KB Output is correct
7 Correct 33 ms 97108 KB Output is correct
8 Correct 31 ms 97336 KB Output is correct
9 Correct 31 ms 97116 KB Output is correct
10 Correct 31 ms 97368 KB Output is correct
11 Correct 30 ms 95320 KB Output is correct
12 Correct 31 ms 97240 KB Output is correct
13 Correct 30 ms 96860 KB Output is correct
14 Correct 30 ms 95068 KB Output is correct
15 Correct 29 ms 97112 KB Output is correct
16 Correct 31 ms 97364 KB Output is correct
17 Correct 30 ms 97116 KB Output is correct
18 Correct 30 ms 95244 KB Output is correct
19 Correct 31 ms 97024 KB Output is correct
20 Correct 32 ms 97168 KB Output is correct
21 Incorrect 28 ms 94968 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 100436 KB Output is correct
2 Correct 372 ms 103300 KB Output is correct
3 Correct 488 ms 103016 KB Output is correct
4 Correct 471 ms 101208 KB Output is correct
5 Correct 408 ms 104372 KB Output is correct
6 Correct 401 ms 104640 KB Output is correct
7 Correct 76 ms 97808 KB Output is correct
8 Correct 61 ms 97892 KB Output is correct
9 Correct 734 ms 98600 KB Output is correct
10 Correct 754 ms 98828 KB Output is correct
11 Correct 748 ms 102440 KB Output is correct
12 Correct 744 ms 100692 KB Output is correct
13 Correct 176 ms 103252 KB Output is correct
14 Correct 252 ms 102020 KB Output is correct
15 Correct 99 ms 105296 KB Output is correct
16 Correct 100 ms 101884 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 97104 KB Output is correct
2 Correct 30 ms 97116 KB Output is correct
3 Correct 32 ms 97116 KB Output is correct
4 Correct 31 ms 97444 KB Output is correct
5 Correct 30 ms 97112 KB Output is correct
6 Correct 27 ms 95068 KB Output is correct
7 Correct 33 ms 97108 KB Output is correct
8 Correct 31 ms 97336 KB Output is correct
9 Correct 31 ms 97116 KB Output is correct
10 Correct 31 ms 97368 KB Output is correct
11 Correct 30 ms 95320 KB Output is correct
12 Correct 31 ms 97240 KB Output is correct
13 Correct 30 ms 96860 KB Output is correct
14 Correct 30 ms 95068 KB Output is correct
15 Correct 29 ms 97112 KB Output is correct
16 Correct 31 ms 97364 KB Output is correct
17 Correct 30 ms 97116 KB Output is correct
18 Correct 30 ms 95244 KB Output is correct
19 Correct 31 ms 97024 KB Output is correct
20 Correct 32 ms 97168 KB Output is correct
21 Correct 479 ms 100436 KB Output is correct
22 Correct 372 ms 103300 KB Output is correct
23 Correct 488 ms 103016 KB Output is correct
24 Correct 471 ms 101208 KB Output is correct
25 Correct 408 ms 104372 KB Output is correct
26 Correct 401 ms 104640 KB Output is correct
27 Correct 76 ms 97808 KB Output is correct
28 Correct 61 ms 97892 KB Output is correct
29 Correct 734 ms 98600 KB Output is correct
30 Correct 754 ms 98828 KB Output is correct
31 Correct 748 ms 102440 KB Output is correct
32 Correct 744 ms 100692 KB Output is correct
33 Correct 176 ms 103252 KB Output is correct
34 Correct 252 ms 102020 KB Output is correct
35 Correct 99 ms 105296 KB Output is correct
36 Correct 100 ms 101884 KB Output is correct
37 Correct 633 ms 108932 KB Output is correct
38 Correct 849 ms 112444 KB Output is correct
39 Correct 84 ms 95824 KB Output is correct
40 Correct 72 ms 97820 KB Output is correct
41 Execution timed out 1016 ms 110324 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 97104 KB Output is correct
2 Correct 30 ms 97116 KB Output is correct
3 Correct 32 ms 97116 KB Output is correct
4 Correct 31 ms 97444 KB Output is correct
5 Correct 30 ms 97112 KB Output is correct
6 Correct 27 ms 95068 KB Output is correct
7 Correct 33 ms 97108 KB Output is correct
8 Correct 31 ms 97336 KB Output is correct
9 Correct 31 ms 97116 KB Output is correct
10 Correct 31 ms 97368 KB Output is correct
11 Correct 30 ms 95320 KB Output is correct
12 Correct 31 ms 97240 KB Output is correct
13 Correct 30 ms 96860 KB Output is correct
14 Correct 30 ms 95068 KB Output is correct
15 Correct 29 ms 97112 KB Output is correct
16 Correct 31 ms 97364 KB Output is correct
17 Correct 30 ms 97116 KB Output is correct
18 Correct 30 ms 95244 KB Output is correct
19 Correct 31 ms 97024 KB Output is correct
20 Correct 32 ms 97168 KB Output is correct
21 Incorrect 28 ms 94968 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 97104 KB Output is correct
2 Correct 30 ms 97116 KB Output is correct
3 Correct 32 ms 97116 KB Output is correct
4 Correct 31 ms 97444 KB Output is correct
5 Correct 30 ms 97112 KB Output is correct
6 Correct 27 ms 95068 KB Output is correct
7 Correct 33 ms 97108 KB Output is correct
8 Correct 31 ms 97336 KB Output is correct
9 Correct 31 ms 97116 KB Output is correct
10 Correct 31 ms 97368 KB Output is correct
11 Correct 30 ms 95320 KB Output is correct
12 Correct 31 ms 97240 KB Output is correct
13 Correct 30 ms 96860 KB Output is correct
14 Correct 30 ms 95068 KB Output is correct
15 Correct 29 ms 97112 KB Output is correct
16 Correct 31 ms 97364 KB Output is correct
17 Correct 30 ms 97116 KB Output is correct
18 Correct 30 ms 95244 KB Output is correct
19 Correct 31 ms 97024 KB Output is correct
20 Correct 32 ms 97168 KB Output is correct
21 Incorrect 28 ms 94968 KB Output isn't correct
22 Halted 0 ms 0 KB -