oj.uz

답안 #547107

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
547107 2022-04-09T14:47:49 Z leaked 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 652 ms 71448 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 && p1[v]==0)
//            return;
        for(auto &u : {v<<1,v<<1|1}){
            if(tt[u].x==p2[v]){
                tt[u].x=p4[v];
                umax(p3[u],p3[v]);
            }else tt[u].x+=p1[v];
//            if(tt[u].x==p2[v]){
//                cout<<"PUSH "<<v<<' '<<u<<endl;
//                tt[u].x=p4[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;
//        push(v,tl,tr);
        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;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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 54484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 54484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 239 ms 61248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 652 ms 71448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 54484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 60760 KB Output is correct
2 Correct 175 ms 61432 KB Output is correct
3 Correct 221 ms 61524 KB Output is correct
4 Correct 169 ms 59336 KB Output is correct
5 Correct 159 ms 60448 KB Output is correct
6 Correct 200 ms 61528 KB Output is correct
7 Correct 128 ms 60708 KB Output is correct
8 Correct 135 ms 60540 KB Output is correct
9 Correct 177 ms 61528 KB Output is correct
10 Correct 164 ms 59208 KB Output is correct
11 Correct 183 ms 61552 KB Output is correct
12 Correct 195 ms 61528 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 54484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 54484 KB Output isn't correct
2 Halted 0 ms 0 KB -