oj.uz

Submission #547136

# Submission time Handle Problem Language Result Execution time Memory
547136 2022-04-09T17:07:44 Z leaked Food Court (JOI21_foodcourt) C++14
13 / 100
 440 ms 61936 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,0);
        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]+=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;umax(tt[v].x,0LL);
            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
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 51948 KB Output is correct
2 Correct 163 ms 51724 KB Output is correct
3 Correct 128 ms 51912 KB Output is correct
4 Correct 126 ms 51980 KB Output is correct
5 Correct 140 ms 51688 KB Output is correct
6 Correct 179 ms 51764 KB Output is correct
7 Correct 62 ms 51356 KB Output is correct
8 Correct 56 ms 51532 KB Output is correct
9 Correct 157 ms 51644 KB Output is correct
10 Correct 206 ms 51696 KB Output is correct
11 Correct 136 ms 51664 KB Output is correct
12 Correct 138 ms 51728 KB Output is correct
13 Incorrect 158 ms 51196 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 45012 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 169 ms 51356 KB Output is correct
2 Correct 209 ms 52032 KB Output is correct
3 Correct 190 ms 52140 KB Output is correct
4 Correct 125 ms 50028 KB Output is correct
5 Correct 197 ms 51140 KB Output is correct
6 Correct 185 ms 52108 KB Output is correct
7 Correct 131 ms 51328 KB Output is correct
8 Correct 130 ms 50832 KB Output is correct
9 Correct 148 ms 52036 KB Output is correct
10 Correct 130 ms 49796 KB Output is correct
11 Correct 207 ms 52108 KB Output is correct
12 Correct 193 ms 52040 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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