oj.uz

Submission #906697

# Submission time Handle Problem Language Result Execution time Memory
906697 2024-01-14T18:36:40 Z alexander707070 Food Court (JOI21_foodcourt) C++14
68 / 100
 1000 ms 168732 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;
long long s,t;
 
long long sz[4*MAXN];
pair<long long,long long> lazy[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);
    }
}

pair<long long,long long> merge_lazy(pair<long long,long long> a,pair<long long,long long> b){
    long long c = min(a.second, b.first);
    a.second -= c;
    b.first -= c;
    a.first += b.first;
    a.second += b.second;
    return a;
}

void psh(int v){

    sz[2*v]-=lazy[v].first;
    sz[2*v]=max(0LL,sz[2*v]);
    sz[2*v]+=lazy[v].second;

    sz[2*v+1]-=lazy[v].first;
    sz[2*v+1]=max(0LL,sz[2*v+1]);
    sz[2*v+1]+=lazy[v].second;

    lazy[2*v]=merge_lazy(lazy[2*v],lazy[v]);
    lazy[2*v+1]=merge_lazy(lazy[2*v+1],lazy[v]);

    lazy[v]={0,0};
}
 
void add(int v,int l,int r,int ll,int rr,long long val){
    if(ll>rr)return;
    psh(v);
 
    if(l==ll and r==rr){
 
        if(val<0){
            sz[v]=max(0LL,sz[v]+val);
            lazy[v].first+=-val;
        }else{
            sz[v]+=val;
            lazy[v].second+=val;
        }

     }else{
        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);
 
        sz[v]=min(sz[2*v],sz[2*v+1]);
    }
}
 
long long getsz(int v,int l,int r,int pos){
    if(l==r)return sz[v];
 
    psh(v);
    int tt=(l+r)/2;
 
    if(pos<=tt)return getsz(2*v,l,tt,pos);
    else return getsz(2*v+1,tt+1,r,pos);
}
 
long long calc(int v,int qr){
    if(tree[v].empty())return 0;
 
    int l=-1,r=tree[v].size(),tt;
 
    while(l+1<r){
        tt=(l+r)/2;
        if(tree[v][tt].tim>=qr){
            r=tt;
        }else{
            l=tt;
        }
    }
 
    if(r>0)return pref[v].back()-pref[v][r-1];
    return pref[v].back();
}
 
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;
        }
    }
 
    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);
            update(1,1,n,l,r,{s,i,t});
        }else if(type==2){
            cin>>l>>r>>s;
            add(1,1,n,l,r,-s);
        }else{
            cin>>s>>t;
            if(getsz(1,1,n,s)<t)cout<<"0\n";
            else cout<<bin(s,getsz(1,1,n,s)-t+1)<<"\n";
        }
    }
 
    return 0;
}

Compilation message

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:153:31: warning: narrowing conversion of 's' from 'long long int' to 'int' [-Wnarrowing]
  153 |             update(1,1,n,l,r,{s,i,t});
      |                               ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 95316 KB Output is correct
2 Correct 32 ms 95296 KB Output is correct
3 Correct 31 ms 95312 KB Output is correct
4 Correct 33 ms 95580 KB Output is correct
5 Correct 30 ms 95064 KB Output is correct
6 Correct 31 ms 95064 KB Output is correct
7 Correct 32 ms 95324 KB Output is correct
8 Correct 32 ms 95320 KB Output is correct
9 Correct 32 ms 95440 KB Output is correct
10 Correct 32 ms 95320 KB Output is correct
11 Correct 32 ms 95324 KB Output is correct
12 Correct 32 ms 95320 KB Output is correct
13 Correct 30 ms 95064 KB Output is correct
14 Correct 30 ms 95068 KB Output is correct
15 Correct 32 ms 95324 KB Output is correct
16 Correct 30 ms 95324 KB Output is correct
17 Correct 31 ms 95316 KB Output is correct
18 Correct 35 ms 95316 KB Output is correct
19 Correct 32 ms 95456 KB Output is correct
20 Correct 32 ms 95452 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 95316 KB Output is correct
2 Correct 32 ms 95296 KB Output is correct
3 Correct 31 ms 95312 KB Output is correct
4 Correct 33 ms 95580 KB Output is correct
5 Correct 30 ms 95064 KB Output is correct
6 Correct 31 ms 95064 KB Output is correct
7 Correct 32 ms 95324 KB Output is correct
8 Correct 32 ms 95320 KB Output is correct
9 Correct 32 ms 95440 KB Output is correct
10 Correct 32 ms 95320 KB Output is correct
11 Correct 32 ms 95324 KB Output is correct
12 Correct 32 ms 95320 KB Output is correct
13 Correct 30 ms 95064 KB Output is correct
14 Correct 30 ms 95068 KB Output is correct
15 Correct 32 ms 95324 KB Output is correct
16 Correct 30 ms 95324 KB Output is correct
17 Correct 31 ms 95316 KB Output is correct
18 Correct 35 ms 95316 KB Output is correct
19 Correct 32 ms 95456 KB Output is correct
20 Correct 32 ms 95452 KB Output is correct
21 Correct 33 ms 95320 KB Output is correct
22 Correct 33 ms 95484 KB Output is correct
23 Correct 34 ms 95416 KB Output is correct
24 Correct 32 ms 95576 KB Output is correct
25 Correct 32 ms 95068 KB Output is correct
26 Correct 31 ms 95068 KB Output is correct
27 Correct 31 ms 95580 KB Output is correct
28 Correct 32 ms 95424 KB Output is correct
29 Correct 31 ms 95316 KB Output is correct
30 Correct 31 ms 95312 KB Output is correct
31 Correct 32 ms 95312 KB Output is correct
32 Correct 32 ms 95324 KB Output is correct
33 Correct 30 ms 95172 KB Output is correct
34 Correct 31 ms 95324 KB Output is correct
35 Correct 31 ms 95316 KB Output is correct
36 Correct 31 ms 95580 KB Output is correct
37 Correct 31 ms 95324 KB Output is correct
38 Correct 31 ms 95312 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 105384 KB Output is correct
2 Correct 109 ms 106836 KB Output is correct
3 Correct 132 ms 106096 KB Output is correct
4 Correct 102 ms 106088 KB Output is correct
5 Correct 113 ms 107664 KB Output is correct
6 Correct 112 ms 107604 KB Output is correct
7 Correct 49 ms 96336 KB Output is correct
8 Correct 56 ms 96572 KB Output is correct
9 Correct 99 ms 105688 KB Output is correct
10 Correct 97 ms 105552 KB Output is correct
11 Correct 99 ms 105524 KB Output is correct
12 Correct 110 ms 105552 KB Output is correct
13 Correct 107 ms 106132 KB Output is correct
14 Correct 138 ms 107052 KB Output is correct
15 Correct 138 ms 108760 KB Output is correct
16 Correct 132 ms 108884 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1109 ms 168732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 95316 KB Output is correct
2 Correct 32 ms 95296 KB Output is correct
3 Correct 31 ms 95312 KB Output is correct
4 Correct 33 ms 95580 KB Output is correct
5 Correct 30 ms 95064 KB Output is correct
6 Correct 31 ms 95064 KB Output is correct
7 Correct 32 ms 95324 KB Output is correct
8 Correct 32 ms 95320 KB Output is correct
9 Correct 32 ms 95440 KB Output is correct
10 Correct 32 ms 95320 KB Output is correct
11 Correct 32 ms 95324 KB Output is correct
12 Correct 32 ms 95320 KB Output is correct
13 Correct 30 ms 95064 KB Output is correct
14 Correct 30 ms 95068 KB Output is correct
15 Correct 32 ms 95324 KB Output is correct
16 Correct 30 ms 95324 KB Output is correct
17 Correct 31 ms 95316 KB Output is correct
18 Correct 35 ms 95316 KB Output is correct
19 Correct 32 ms 95456 KB Output is correct
20 Correct 32 ms 95452 KB Output is correct
21 Correct 115 ms 105384 KB Output is correct
22 Correct 109 ms 106836 KB Output is correct
23 Correct 132 ms 106096 KB Output is correct
24 Correct 102 ms 106088 KB Output is correct
25 Correct 113 ms 107664 KB Output is correct
26 Correct 112 ms 107604 KB Output is correct
27 Correct 49 ms 96336 KB Output is correct
28 Correct 56 ms 96572 KB Output is correct
29 Correct 99 ms 105688 KB Output is correct
30 Correct 97 ms 105552 KB Output is correct
31 Correct 99 ms 105524 KB Output is correct
32 Correct 110 ms 105552 KB Output is correct
33 Correct 107 ms 106132 KB Output is correct
34 Correct 138 ms 107052 KB Output is correct
35 Correct 138 ms 108760 KB Output is correct
36 Correct 132 ms 108884 KB Output is correct
37 Correct 218 ms 111868 KB Output is correct
38 Correct 207 ms 115520 KB Output is correct
39 Correct 48 ms 96340 KB Output is correct
40 Correct 60 ms 96392 KB Output is correct
41 Correct 245 ms 115032 KB Output is correct
42 Correct 270 ms 115376 KB Output is correct
43 Correct 208 ms 115012 KB Output is correct
44 Correct 218 ms 115140 KB Output is correct
45 Correct 222 ms 115152 KB Output is correct
46 Correct 255 ms 114940 KB Output is correct
47 Correct 101 ms 99720 KB Output is correct
48 Correct 137 ms 112888 KB Output is correct
49 Correct 139 ms 111404 KB Output is correct
50 Correct 189 ms 113492 KB Output is correct
51 Correct 214 ms 115500 KB Output is correct
52 Correct 225 ms 115928 KB Output is correct
53 Correct 100 ms 107348 KB Output is correct
54 Correct 138 ms 108892 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 117216 KB Output is correct
2 Correct 335 ms 118196 KB Output is correct
3 Correct 372 ms 118996 KB Output is correct
4 Correct 223 ms 114452 KB Output is correct
5 Correct 275 ms 117056 KB Output is correct
6 Correct 355 ms 119804 KB Output is correct
7 Correct 67 ms 97096 KB Output is correct
8 Correct 80 ms 96848 KB Output is correct
9 Correct 131 ms 100872 KB Output is correct
10 Correct 132 ms 111996 KB Output is correct
11 Correct 204 ms 118116 KB Output is correct
12 Correct 197 ms 118320 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 95316 KB Output is correct
2 Correct 32 ms 95296 KB Output is correct
3 Correct 31 ms 95312 KB Output is correct
4 Correct 33 ms 95580 KB Output is correct
5 Correct 30 ms 95064 KB Output is correct
6 Correct 31 ms 95064 KB Output is correct
7 Correct 32 ms 95324 KB Output is correct
8 Correct 32 ms 95320 KB Output is correct
9 Correct 32 ms 95440 KB Output is correct
10 Correct 32 ms 95320 KB Output is correct
11 Correct 32 ms 95324 KB Output is correct
12 Correct 32 ms 95320 KB Output is correct
13 Correct 30 ms 95064 KB Output is correct
14 Correct 30 ms 95068 KB Output is correct
15 Correct 32 ms 95324 KB Output is correct
16 Correct 30 ms 95324 KB Output is correct
17 Correct 31 ms 95316 KB Output is correct
18 Correct 35 ms 95316 KB Output is correct
19 Correct 32 ms 95456 KB Output is correct
20 Correct 32 ms 95452 KB Output is correct
21 Correct 33 ms 95320 KB Output is correct
22 Correct 33 ms 95484 KB Output is correct
23 Correct 34 ms 95416 KB Output is correct
24 Correct 32 ms 95576 KB Output is correct
25 Correct 32 ms 95068 KB Output is correct
26 Correct 31 ms 95068 KB Output is correct
27 Correct 31 ms 95580 KB Output is correct
28 Correct 32 ms 95424 KB Output is correct
29 Correct 31 ms 95316 KB Output is correct
30 Correct 31 ms 95312 KB Output is correct
31 Correct 32 ms 95312 KB Output is correct
32 Correct 32 ms 95324 KB Output is correct
33 Correct 30 ms 95172 KB Output is correct
34 Correct 31 ms 95324 KB Output is correct
35 Correct 31 ms 95316 KB Output is correct
36 Correct 31 ms 95580 KB Output is correct
37 Correct 31 ms 95324 KB Output is correct
38 Correct 31 ms 95312 KB Output is correct
39 Correct 115 ms 105384 KB Output is correct
40 Correct 109 ms 106836 KB Output is correct
41 Correct 132 ms 106096 KB Output is correct
42 Correct 102 ms 106088 KB Output is correct
43 Correct 113 ms 107664 KB Output is correct
44 Correct 112 ms 107604 KB Output is correct
45 Correct 49 ms 96336 KB Output is correct
46 Correct 56 ms 96572 KB Output is correct
47 Correct 99 ms 105688 KB Output is correct
48 Correct 97 ms 105552 KB Output is correct
49 Correct 99 ms 105524 KB Output is correct
50 Correct 110 ms 105552 KB Output is correct
51 Correct 107 ms 106132 KB Output is correct
52 Correct 138 ms 107052 KB Output is correct
53 Correct 138 ms 108760 KB Output is correct
54 Correct 132 ms 108884 KB Output is correct
55 Correct 218 ms 111868 KB Output is correct
56 Correct 207 ms 115520 KB Output is correct
57 Correct 48 ms 96340 KB Output is correct
58 Correct 60 ms 96392 KB Output is correct
59 Correct 245 ms 115032 KB Output is correct
60 Correct 270 ms 115376 KB Output is correct
61 Correct 208 ms 115012 KB Output is correct
62 Correct 218 ms 115140 KB Output is correct
63 Correct 222 ms 115152 KB Output is correct
64 Correct 255 ms 114940 KB Output is correct
65 Correct 101 ms 99720 KB Output is correct
66 Correct 137 ms 112888 KB Output is correct
67 Correct 139 ms 111404 KB Output is correct
68 Correct 189 ms 113492 KB Output is correct
69 Correct 214 ms 115500 KB Output is correct
70 Correct 225 ms 115928 KB Output is correct
71 Correct 100 ms 107348 KB Output is correct
72 Correct 138 ms 108892 KB Output is correct
73 Correct 284 ms 117216 KB Output is correct
74 Correct 335 ms 118196 KB Output is correct
75 Correct 372 ms 118996 KB Output is correct
76 Correct 223 ms 114452 KB Output is correct
77 Correct 275 ms 117056 KB Output is correct
78 Correct 355 ms 119804 KB Output is correct
79 Correct 67 ms 97096 KB Output is correct
80 Correct 80 ms 96848 KB Output is correct
81 Correct 131 ms 100872 KB Output is correct
82 Correct 132 ms 111996 KB Output is correct
83 Correct 204 ms 118116 KB Output is correct
84 Correct 197 ms 118320 KB Output is correct
85 Correct 190 ms 112672 KB Output is correct
86 Correct 232 ms 114260 KB Output is correct
87 Correct 228 ms 117316 KB Output is correct
88 Correct 264 ms 119680 KB Output is correct
89 Correct 177 ms 110932 KB Output is correct
90 Correct 222 ms 115780 KB Output is correct
91 Correct 166 ms 112716 KB Output is correct
92 Correct 173 ms 112080 KB Output is correct
93 Correct 210 ms 115592 KB Output is correct
94 Correct 250 ms 115876 KB Output is correct
95 Correct 230 ms 115240 KB Output is correct
96 Correct 221 ms 115644 KB Output is correct
97 Correct 241 ms 115688 KB Output is correct
98 Correct 166 ms 113228 KB Output is correct
99 Correct 91 ms 100312 KB Output is correct
100 Correct 133 ms 110508 KB Output is correct
101 Correct 145 ms 113388 KB Output is correct
102 Correct 141 ms 111416 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 95316 KB Output is correct
2 Correct 32 ms 95296 KB Output is correct
3 Correct 31 ms 95312 KB Output is correct
4 Correct 33 ms 95580 KB Output is correct
5 Correct 30 ms 95064 KB Output is correct
6 Correct 31 ms 95064 KB Output is correct
7 Correct 32 ms 95324 KB Output is correct
8 Correct 32 ms 95320 KB Output is correct
9 Correct 32 ms 95440 KB Output is correct
10 Correct 32 ms 95320 KB Output is correct
11 Correct 32 ms 95324 KB Output is correct
12 Correct 32 ms 95320 KB Output is correct
13 Correct 30 ms 95064 KB Output is correct
14 Correct 30 ms 95068 KB Output is correct
15 Correct 32 ms 95324 KB Output is correct
16 Correct 30 ms 95324 KB Output is correct
17 Correct 31 ms 95316 KB Output is correct
18 Correct 35 ms 95316 KB Output is correct
19 Correct 32 ms 95456 KB Output is correct
20 Correct 32 ms 95452 KB Output is correct
21 Correct 33 ms 95320 KB Output is correct
22 Correct 33 ms 95484 KB Output is correct
23 Correct 34 ms 95416 KB Output is correct
24 Correct 32 ms 95576 KB Output is correct
25 Correct 32 ms 95068 KB Output is correct
26 Correct 31 ms 95068 KB Output is correct
27 Correct 31 ms 95580 KB Output is correct
28 Correct 32 ms 95424 KB Output is correct
29 Correct 31 ms 95316 KB Output is correct
30 Correct 31 ms 95312 KB Output is correct
31 Correct 32 ms 95312 KB Output is correct
32 Correct 32 ms 95324 KB Output is correct
33 Correct 30 ms 95172 KB Output is correct
34 Correct 31 ms 95324 KB Output is correct
35 Correct 31 ms 95316 KB Output is correct
36 Correct 31 ms 95580 KB Output is correct
37 Correct 31 ms 95324 KB Output is correct
38 Correct 31 ms 95312 KB Output is correct
39 Correct 115 ms 105384 KB Output is correct
40 Correct 109 ms 106836 KB Output is correct
41 Correct 132 ms 106096 KB Output is correct
42 Correct 102 ms 106088 KB Output is correct
43 Correct 113 ms 107664 KB Output is correct
44 Correct 112 ms 107604 KB Output is correct
45 Correct 49 ms 96336 KB Output is correct
46 Correct 56 ms 96572 KB Output is correct
47 Correct 99 ms 105688 KB Output is correct
48 Correct 97 ms 105552 KB Output is correct
49 Correct 99 ms 105524 KB Output is correct
50 Correct 110 ms 105552 KB Output is correct
51 Correct 107 ms 106132 KB Output is correct
52 Correct 138 ms 107052 KB Output is correct
53 Correct 138 ms 108760 KB Output is correct
54 Correct 132 ms 108884 KB Output is correct
55 Execution timed out 1109 ms 168732 KB Time limit exceeded
56 Halted 0 ms 0 KB -