oj.uz

Submission #547139

# Submission time Handle Problem Language Result Execution time Memory
547139 2022-04-09T17:10:01 Z leaked Food Court (JOI21_foodcourt) C++14
37 / 100
 630 ms 61968 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//#define int long long
//#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
const ll inf=1e18;
const int N=3e5+1;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
struct fenwick{
    ll fnw[N];
    fenwick(){
        fill(fnw,fnw+N,0);
    }
    void reset(){
        fill(fnw,fnw+N,0);
    }
    void upd(int i,int x){
        ++i;
        while(i<N){
            fnw[i]+=x;
            i+=i&-i;
        }
    }
    ll get(int i){
        ++i;
        ll ans=0;
        while(i>0){
            ans+=fnw[i];
            i-=i&-i;
        }
        return ans;
    }
    void add(int l,int r,ll x){
        upd(l,x);
        upd(r+1,-x);
    }
};

struct segtree{
    ll p1[4*N],p4[4*N];
    ///add,whom,to_set
    int p3[4*N];
    struct node{
        ll x,y;
        node(){
            x=0,y=inf;
        }
    };
    node mg(node a,node b){
        if(a.x>b.x) swap(a.x,b.x);
        if(b.x>b.y) swap(b.x,b.y);
        if(a.x==b.x) umin(a.y,b.y);
        else umin(a.y,b.x);
        return a;
    }
    node tt[4*N];
    segtree(){
        fill(p1,p1+4*N,0);
        fill(p4,p4+4*N,inf);
        fill(p3,p3+4*N,-1);
    }
    bool check(ll a,ll b,ll c){
        if((a+c)<=0 && (b+c)<=0)
            return 0;
        return 1;
    }
    void push(int v,int tl,int tr){
        int mn=min(tt[2*v].x,tt[2*v+1].x);
        for(auto &u : {v<<1,v<<1|1}){
            if(tt[u].x==mn && p4[v]!=inf){
                tt[u].x=p4[v];
                umax(p3[u],p3[v]);
                p4[u]=p4[v];
            }else tt[u].x+=p1[v],p4[u]=(p4[u]==inf?inf:p4[u]+p1[v]);
            tt[u].y+=p1[v];
            p1[u]+=p1[v];
        }
        p1[v]=0;p4[v]=inf;
    }

    void add(int l,int r,int x,int t,int v,int tl,int tr){
        if(tl>r||tr<l) return;
        if(tl>=l&&tr<=r&&check(tt[v].x,tt[v].y,x)){
            tt[v].x+=x;
            if((tt[v].x)<0){
                umax(p3[v],t);
            }
            tt[v].y+=x;
            p1[v]+=x;
            if(umax(tt[v].x,0LL) || p4[v]!=inf)
                p4[v]=tt[v].x;
            return;
        }
        int tm=(tl+tr)>>1;push(v,tl,tr);
        add(l,r,x,t,v<<1,tl,tm);add(l,r,x,t,v<<1|1,tm+1,tr);
        tt[v]=mg(tt[2*v],tt[2*v+1]);
    }
    int get(int i,int v,int tl,int tr){
        if(tl==tr)
            return p3[v];
        int tm=(tl+tr)>>1;push(v,tl,tr);
        if(tm>=i)
            return get(i,v<<1,tl,tm);
        else
            return get(i,v<<1|1,tm+1,tr);
    }
}sega1;
signed main(){
    fast_prep;
    int n,m,q;
    cin>>n>>m>>q;
    fenwick fen;
    vec<int> tl(q),tr(q);
    vec<int> t(q),l(q),r(q),c(q);
    vec<ll> k(q);
    vec<int> ask;
    vec<ll> rl(q);

    vec<ll> toadd(q);
    vec<vec<int>> need(q,vec<int>());
    for(int i=0;i<q;i++){
        cin>>t[i];
        if(t[i]==1){
            cin>>l[i]>>r[i]>>c[i]>>k[i];
            --l[i];--r[i];
            sega1.add(l[i],r[i],k[i],i,1,0,n-1);
        }
        else if(t[i]==2){
            cin>>l[i]>>r[i]>>k[i];
            --l[i];--r[i];
            fen.add(l[i],r[i],k[i]);
            sega1.add(l[i],r[i],-k[i],i,1,0,n-1);
        }
        else{
            ask.pb(i);
            cin>>l[i]>>k[i];
            --l[i];
            rl[i]=fen.get(l[i])+k[i];
//            cerr<<"ALO "<<
//            cerr<<"WO "<<sega1.get(l[i],1,0,n-1)<<endl;
            tl[i]=sega1.get(l[i],1,0,n-1)+1;tr[i]=i;
//            cout<<"ALO "<<tl[i]<<endl;
            if(tl[i]!=0) need[tl[i]-1].pb(i);
        }
//        sega1.get(977,1,0,n-1);
    }
    {
        fen.reset();
        for(int i=0;i<q;i++){
            if(t[i]==1) fen.add(l[i],r[i],k[i]);
            else if(t[i]==2) fen.add(l[i],r[i],-k[i]);
            for(auto &j : need[i]){
                toadd[j]=-fen.get(l[j]);
            }
        }
    }
    if(m==1){
        fen.reset();
        for(int i=0;i<q;i++){
            if(t[i]==1) fen.add(l[i],r[i],k[i]);
            else if(t[i]==3){
                if((fen.get(l[i])+toadd[i])>=rl[i]){
                    cout<<1<<'\n';
                }
                else{
                    cout<<0<<'\n';
                }
            }
        }
        return 0;
    }
    int ok=1;
    while(ok){
        ok=0;
        fen.reset();
        vec<vec<int>> toask(q,vec<int>());
        ///just an id
        for(auto &i : ask){
            if(tl[i]!=tr[i]){
                int tm=(tl[i]+tr[i])>>1;
//                cout<<"HEYASK "<<i<<' '<<tl[i]<<' '<<tr[i]<<' '<<tm<<endl;
                ok=1;
                toask[tm].pb(i);
            }
        }
        if(!ok) break;
        for(int i=0;i<q;i++){
            if(t[i]==1){
                fen.add(l[i],r[i],k[i]);
            }
//            cout<<"I "<<i<<endl;
            for(auto &j : toask[i]){
                ll have=fen.get(l[j])+toadd[j];
//                cout<<"YO "<<c[i]<<' '<<j<<' '<<have<<' '<<rl[j]<<endl;
                if(have>=rl[j]){
                    tr[j]=i;
                }
                else{
                    tl[j]=i+1;
                }
            }
        }
    }
    for(auto &i : ask){
        cout<<(tl[i]==i?0:c[tl[i]])<<'\n';
    }
    return 0;
}
/*
1457 1000 3
2 253 1112 1
1 872 1007 206029 1
3 978 1

3 5 5
1 2 3 5 2
1 1 2 2 4
2 1 3 3
1 2 3 4 2
3 3 2

3 5 5
1 2 3 5 2
1 1 2 2 4
2 1 3 3
3 1 2
1 2 3 4 2

*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45044 KB Output is correct
2 Correct 22 ms 45140 KB Output is correct
3 Correct 24 ms 45008 KB Output is correct
4 Correct 23 ms 45124 KB Output is correct
5 Correct 21 ms 45052 KB Output is correct
6 Correct 22 ms 45120 KB Output is correct
7 Correct 21 ms 45048 KB Output is correct
8 Correct 28 ms 45188 KB Output is correct
9 Correct 23 ms 45132 KB Output is correct
10 Correct 25 ms 45148 KB Output is correct
11 Correct 22 ms 45012 KB Output is correct
12 Correct 22 ms 45140 KB Output is correct
13 Correct 20 ms 45020 KB Output is correct
14 Correct 21 ms 45140 KB Output is correct
15 Correct 21 ms 45004 KB Output is correct
16 Correct 23 ms 45140 KB Output is correct
17 Correct 25 ms 45072 KB Output is correct
18 Correct 23 ms 45068 KB Output is correct
19 Correct 22 ms 45112 KB Output is correct
20 Correct 23 ms 45140 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45044 KB Output is correct
2 Correct 22 ms 45140 KB Output is correct
3 Correct 24 ms 45008 KB Output is correct
4 Correct 23 ms 45124 KB Output is correct
5 Correct 21 ms 45052 KB Output is correct
6 Correct 22 ms 45120 KB Output is correct
7 Correct 21 ms 45048 KB Output is correct
8 Correct 28 ms 45188 KB Output is correct
9 Correct 23 ms 45132 KB Output is correct
10 Correct 25 ms 45148 KB Output is correct
11 Correct 22 ms 45012 KB Output is correct
12 Correct 22 ms 45140 KB Output is correct
13 Correct 20 ms 45020 KB Output is correct
14 Correct 21 ms 45140 KB Output is correct
15 Correct 21 ms 45004 KB Output is correct
16 Correct 23 ms 45140 KB Output is correct
17 Correct 25 ms 45072 KB Output is correct
18 Correct 23 ms 45068 KB Output is correct
19 Correct 22 ms 45112 KB Output is correct
20 Correct 23 ms 45140 KB Output is correct
21 Incorrect 22 ms 45036 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 141 ms 51996 KB Output is correct
2 Correct 152 ms 51724 KB Output is correct
3 Correct 131 ms 51928 KB Output is correct
4 Correct 137 ms 51912 KB Output is correct
5 Correct 156 ms 51728 KB Output is correct
6 Correct 145 ms 51728 KB Output is correct
7 Correct 56 ms 51428 KB Output is correct
8 Correct 57 ms 51532 KB Output is correct
9 Correct 120 ms 51668 KB Output is correct
10 Correct 132 ms 51672 KB Output is correct
11 Correct 125 ms 51672 KB Output is correct
12 Correct 131 ms 51664 KB Output is correct
13 Correct 126 ms 51220 KB Output is correct
14 Correct 147 ms 51904 KB Output is correct
15 Correct 147 ms 51308 KB Output is correct
16 Correct 149 ms 51416 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45044 KB Output is correct
2 Correct 22 ms 45140 KB Output is correct
3 Correct 24 ms 45008 KB Output is correct
4 Correct 23 ms 45124 KB Output is correct
5 Correct 21 ms 45052 KB Output is correct
6 Correct 22 ms 45120 KB Output is correct
7 Correct 21 ms 45048 KB Output is correct
8 Correct 28 ms 45188 KB Output is correct
9 Correct 23 ms 45132 KB Output is correct
10 Correct 25 ms 45148 KB Output is correct
11 Correct 22 ms 45012 KB Output is correct
12 Correct 22 ms 45140 KB Output is correct
13 Correct 20 ms 45020 KB Output is correct
14 Correct 21 ms 45140 KB Output is correct
15 Correct 21 ms 45004 KB Output is correct
16 Correct 23 ms 45140 KB Output is correct
17 Correct 25 ms 45072 KB Output is correct
18 Correct 23 ms 45068 KB Output is correct
19 Correct 22 ms 45112 KB Output is correct
20 Correct 23 ms 45140 KB Output is correct
21 Correct 141 ms 51996 KB Output is correct
22 Correct 152 ms 51724 KB Output is correct
23 Correct 131 ms 51928 KB Output is correct
24 Correct 137 ms 51912 KB Output is correct
25 Correct 156 ms 51728 KB Output is correct
26 Correct 145 ms 51728 KB Output is correct
27 Correct 56 ms 51428 KB Output is correct
28 Correct 57 ms 51532 KB Output is correct
29 Correct 120 ms 51668 KB Output is correct
30 Correct 132 ms 51672 KB Output is correct
31 Correct 125 ms 51672 KB Output is correct
32 Correct 131 ms 51664 KB Output is correct
33 Correct 126 ms 51220 KB Output is correct
34 Correct 147 ms 51904 KB Output is correct
35 Correct 147 ms 51308 KB Output is correct
36 Correct 149 ms 51416 KB Output is correct
37 Correct 153 ms 51180 KB Output is correct
38 Correct 131 ms 50232 KB Output is correct
39 Correct 93 ms 50536 KB Output is correct
40 Correct 101 ms 51260 KB Output is correct
41 Correct 157 ms 51624 KB Output is correct
42 Correct 158 ms 51608 KB Output is correct
43 Correct 181 ms 51932 KB Output is correct
44 Correct 163 ms 51660 KB Output is correct
45 Correct 166 ms 51668 KB Output is correct
46 Correct 171 ms 51640 KB Output is correct
47 Correct 104 ms 52020 KB Output is correct
48 Correct 147 ms 51924 KB Output is correct
49 Correct 125 ms 49620 KB Output is correct
50 Correct 180 ms 50636 KB Output is correct
51 Correct 194 ms 51620 KB Output is correct
52 Correct 182 ms 51672 KB Output is correct
53 Correct 123 ms 50040 KB Output is correct
54 Correct 169 ms 51388 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 51252 KB Output is correct
2 Correct 200 ms 52036 KB Output is correct
3 Correct 191 ms 52136 KB Output is correct
4 Correct 130 ms 49940 KB Output is correct
5 Correct 151 ms 51052 KB Output is correct
6 Correct 173 ms 52140 KB Output is correct
7 Correct 132 ms 51228 KB Output is correct
8 Correct 116 ms 50924 KB Output is correct
9 Correct 142 ms 52032 KB Output is correct
10 Correct 119 ms 49908 KB Output is correct
11 Correct 178 ms 52172 KB Output is correct
12 Correct 171 ms 52036 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45044 KB Output is correct
2 Correct 22 ms 45140 KB Output is correct
3 Correct 24 ms 45008 KB Output is correct
4 Correct 23 ms 45124 KB Output is correct
5 Correct 21 ms 45052 KB Output is correct
6 Correct 22 ms 45120 KB Output is correct
7 Correct 21 ms 45048 KB Output is correct
8 Correct 28 ms 45188 KB Output is correct
9 Correct 23 ms 45132 KB Output is correct
10 Correct 25 ms 45148 KB Output is correct
11 Correct 22 ms 45012 KB Output is correct
12 Correct 22 ms 45140 KB Output is correct
13 Correct 20 ms 45020 KB Output is correct
14 Correct 21 ms 45140 KB Output is correct
15 Correct 21 ms 45004 KB Output is correct
16 Correct 23 ms 45140 KB Output is correct
17 Correct 25 ms 45072 KB Output is correct
18 Correct 23 ms 45068 KB Output is correct
19 Correct 22 ms 45112 KB Output is correct
20 Correct 23 ms 45140 KB Output is correct
21 Incorrect 22 ms 45036 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45044 KB Output is correct
2 Correct 22 ms 45140 KB Output is correct
3 Correct 24 ms 45008 KB Output is correct
4 Correct 23 ms 45124 KB Output is correct
5 Correct 21 ms 45052 KB Output is correct
6 Correct 22 ms 45120 KB Output is correct
7 Correct 21 ms 45048 KB Output is correct
8 Correct 28 ms 45188 KB Output is correct
9 Correct 23 ms 45132 KB Output is correct
10 Correct 25 ms 45148 KB Output is correct
11 Correct 22 ms 45012 KB Output is correct
12 Correct 22 ms 45140 KB Output is correct
13 Correct 20 ms 45020 KB Output is correct
14 Correct 21 ms 45140 KB Output is correct
15 Correct 21 ms 45004 KB Output is correct
16 Correct 23 ms 45140 KB Output is correct
17 Correct 25 ms 45072 KB Output is correct
18 Correct 23 ms 45068 KB Output is correct
19 Correct 22 ms 45112 KB Output is correct
20 Correct 23 ms 45140 KB Output is correct
21 Incorrect 22 ms 45036 KB Output isn't correct
22 Halted 0 ms 0 KB -