Submission #547148

#	Time	Username	Problem	Language	Result	Execution time	Memory
547148		leaked	Food Court (JOI21_foodcourt)	C++14	100 / 100	956 ms	134212 KiB

foodcourt

#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 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){
        ll 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,ll 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;
struct node1{
    ll s,s1,s2;
    ll mxpref;
    node1(){
        s=0,s1=0,s2=0;
        mxpref=0;
    }
};
node1 mg(node1 a,node1 b){
    node1 c;
    c.s=a.s+b.s;
    c.s1=a.s1+b.s1;
    c.s2=a.s2+b.s2;
    c.mxpref=max({a.mxpref,b.mxpref+a.s1});
    return c;
}
struct segat{
    node1 t[4*N];
    void upd(int i,ll x,int tp,int v,int tl,int tr){
        if(tl==tr){
            t[v].s+=tp*x;
            if(x<0) t[v].s2+=tp*-x;
            else t[v].s1+=tp*x;

            t[v].mxpref=t[v].s1;
//            umax(t[v].mxpref,0LL);
//            umin(t[v].mnpref,0LL);
//            cout<<"E "<<tl<<' '<<tr<<' '<<t[v].s2<<' '<<t[v]endl;
            return;
        }
        int tm=(tl+tr)>>1;
        if(tm>=i)
            upd(i,x,tp,v<<1,tl,tm);
        else
            upd(i,x,tp,v<<1|1,tm+1,tr);
        t[v]=mg(t[2*v],t[2*v+1]);
    }
    int findj1(ll x,int i,ll wt,int v,int tl,int tr){
        if(tr<i)
            return -1;
        if(tl>=i){
            if((x+t[v].mxpref)<wt)
                return -1;
        }
        if(tl==tr) return tl;
        int tm=(tl+tr)>>1;

        int j=findj1(x,i,wt,2*v,tl,tm);
        if(j!=-1) return j;
        return findj1(x+t[2*v].s1,i,wt,2*v+1,tm+1,tr);
    }
    node1 emp;
    node1 gets(int l,int r,int v,int tl,int tr){
//        cout<<l<<' '<<r<<' '<<"TL "<<tl<<' '<<tr<<' '<<t[v].s<<endl;
        if(tl>=l&&tr<=r)
            return t[v];
        if(tl>r||tr<l)
            return emp;
        int tm=(tl+tr)>>1;
        return mg(gets(l,r,2*v,tl,tm),gets(l,r,2*v+1,tm+1,tr));
    }
}sega;
signed main(){
    fast_prep;
    int n,m,q;
    cin>>n>>m>>q;
    vec<int> t(q),l(q),r(q),c(q);
    vec<ll> k(q);
    vec<ll> rl(q);
    vec<vec<int>> rs(n,vec<int>());
    vec<vec<int>> ls(n,vec<int>());
    vec<vec<int>> asks(n,vec<int>());
    vec<int>ans(q);
    vec<int> js(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);
            ls[l[i]].pb(i);
            rs[r[i]].pb(i);
        }
        else if(t[i]==2){
            cin>>l[i]>>r[i]>>k[i];
            --l[i];--r[i];
            sega1.add(l[i],r[i],-k[i],i,1,0,n-1);
            ls[l[i]].pb(i);rs[r[i]].pb(i);
        }
        else{
            cin>>l[i]>>k[i];
            --l[i];
            js[i]=sega1.get(l[i],1,0,n-1);
            asks[l[i]].pb(i);
        }
    }

    vec<int> ids(q);
    for(int i=0;i<n;i++){
        for(auto &j : ls[i]){
            if(t[j]==1) sega.upd(j,k[j],1,1,0,q-1);
            else sega.upd(j,-k[j],1,1,0,q-1);
        }
        for(auto &j : asks[i]){
            int f=js[j];
            ++f;
            node1 that=sega.gets(0,f-1,1,0,q-1);
            ll toadd=-that.s;
            ll need=sega.gets(0,j,1,0,q-1).s2+k[j];
            int s=sega.findj1(toadd,f,need,1,0,q-1);
            if(s==-1 || s>=j) ans[j]=0;
            else ans[j]=c[s];
        }
        for(auto &j : rs[i]){
            if(t[j]==1) sega.upd(j,k[j],-1,1,0,q-1);
            else sega.upd(j,-k[j],-1,1,0,q-1);
        }
    }
    for(int i=0;i<q;i++){
        if(t[i]==3) cout<<ans[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 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11