oj.uz

Submission #547102

# Submission time Handle Problem Language Result Execution time Memory
547102 2022-04-09T14:28:32 Z leaked Food Court (JOI21_foodcourt) C++14
13 / 100
 576 ms 71780 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],p2[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(p2,p2+4*N,-inf);
        fill(p4,p4+4*N,0);
        fill(p3,p3+4*N,-1);
    }
    void push(int v,int tl,int tr){
        if(p2[v]==-inf) return;
        for(auto &u : {v<<1,v<<1|1}){
            if(tt[u].x==p2[v]){
//                cout<<"PUSH "<<v<<' '<<u<<endl;
                tt[u].x=p4[v];
                tt[u].y+=p1[v];
                umax(p3[u],p3[v]);
            }else{
                tt[u].x+=p1[v];
                tt[u].y+=p1[v];
            }

            p2[u]=p2[v];
            p4[u]=p4[v];
            p1[u]+=p1[v];
        }
        p1[v]=0;p2[v]=-inf;
    }
    bool check(ll a,ll b,ll c){
        if((a+c)<=0 && (b+c)<=0)
            return 0;
        return 1;
    }
    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)){
            if((tt[v].x+x)<0){
                p2[v]=(p2[v]==-inf?tt[v].x:p2[v]);
                umax(p3[v],t);

            }
            tt[v].x+=x;tt[v].y+=x;

            p1[v]+=x;
//            cout<<"HERE "<<tl<<' '<<tr<<endl;
            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 "<<sega.get(l[i],1,0,n-1);
            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);
        }
    }
    {
        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;
}
/*
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 24 ms 54484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 61304 KB Output is correct
2 Correct 138 ms 61164 KB Output is correct
3 Correct 135 ms 61272 KB Output is correct
4 Correct 126 ms 61316 KB Output is correct
5 Correct 163 ms 61180 KB Output is correct
6 Correct 144 ms 61144 KB Output is correct
7 Correct 62 ms 60748 KB Output is correct
8 Incorrect 69 ms 60960 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 54484 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 160 ms 60944 KB Output is correct
2 Correct 186 ms 61432 KB Output is correct
3 Correct 172 ms 61496 KB Output is correct
4 Correct 129 ms 59340 KB Output is correct
5 Correct 148 ms 60584 KB Output is correct
6 Correct 171 ms 61472 KB Output is correct
7 Correct 130 ms 60732 KB Output is correct
8 Correct 122 ms 60372 KB Output is correct
9 Correct 139 ms 61512 KB Output is correct
10 Correct 113 ms 59176 KB Output is correct
11 Correct 174 ms 61444 KB Output is correct
12 Correct 164 ms 61508 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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