Submission #1296567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296567		viyeuquadamdau	Food Court (JOI21_foodcourt)	C++20	100 / 100	654 ms	69108 KiB

foodcourt

#pragma GCC optimize("O3")

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define vec vector
#define PB push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define ull unsigned long long
#define pii pair<int, int>
#define rz resize
#define ld long double  
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define matrix vec<vec<int>>
#define MP make_pair

const int N = 250004;
const int M = 2e14;
const int MAXN=1e7;
const ll INF = 1e18;
const ll mod = 1e9+7;

mt19937_64 rng(time(0));
int random(int a, int b) {return uniform_int_distribution<ll>(a,b)(rng);}

void minz(int &a, int b){
    if(a>b)a=b;
}

void maxz(int& a, int b){
    if(b>a)a=b;
}

struct Fenwick
{
    vec<int> f;
    int n;
    Fenwick(int _n){
        n=_n;f.rz(n+5);
    }
    void upd(int x, int v){
        for(;x<=n;x+=x&-x)f[x]+=v;
    }
    void upd(int l, int r, int v){
        upd(l,v); upd(r+1,-v);
    }
    int quer(int x){
        int r=0;
        for(;x>0;x-=x&-x)r+=f[x]; return r;
    }
    int quer(int l, int r){
        return quer(r)-quer(l-1);
    }
};

struct SegmentTree
{
    vec<int>s1,s2;
    int n;
    SegmentTree(int _n){
        n=_n;s1.rz(4*n+5);s2.rz(4*n+5);
    }
    void add(int id, int x, int y){
        s1[id]+=x;
        s2[id]=max(s2[id]+x,y);
    }
    void pull(int id, int l, int r){
        if(l==r) return;
        if(l!=r){
            add(id<<1,s1[id],s2[id]);
            add(id<<1|1,s1[id],s2[id]);
        }
        s1[id]=s2[id]=0;
    }

    void upd(int id, int l, int r, int cl, int cr, int x){
        pull(id,l,r);
        if(l > cr || r<cl)return;
        if(l >= cl && r<=cr){
            add(id,x,0); return ;
        }
        int m=(l+r)>>1;
        upd(id<<1,l,m,cl,cr,x);upd(id<<1|1,m+1,r,cl,cr,x);
    }

    void upd(int l, int r, int x){
        upd(1,1,n,l,r,x);
    }

    int quer(int id, int l, int r, int x){
        pull(id,l,r);
        if(l==r){
            return max(s1[id],s2[id]);
        }
        int m=(l+r)>>1;
        if(m >= x) return quer(id<<1,l,m,x);
        return quer(id<<1|1,m+1,r,x);
    }

    int quer(int pos){
        return quer(1,1,n,pos);
    }
};

int type[N];
int L[N],R[N],C[N],K[N],A[N],B[N];
int n,m,q;

bool chk(int m, int a, int b){
    Fenwick f(n);
    for(int i=0;i<=m;++i){
        if(type[i]==1){
            f.upd(L[i],R[i],K[i]);
        }
    }
    // return 1;
    return (f.quer(a)>=b);
}

vec<int> quers[N];
vec<int> nquers[N];
int l[N],r[N],an[N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("CUTSEQ.INP","r",stdin);
    // freopen("CUTSEQ.out","w",stdout);

    cin>>n>>m>>q;
    Fenwick fen(n);
    SegmentTree seg(n);

    for(int i=0;i<q;++i){
        cin>>type[i];
        if(type[i]==1){
            cin >>L[i]>>R[i]>>C[i]>>K[i];
            fen.upd(L[i],R[i],K[i]);
            seg.upd(L[i],R[i],K[i]);
        } else if(type[i]==2){
            cin>>L[i]>>R[i]>>K[i];
            seg.upd(L[i],R[i],-K[i]);
        } else {
            cin>>A[i]>>B[i];
            B[i] += fen.quer(A[i])-seg.quer(A[i]);
            l[i]=0,r[i]=i-1;
            quers[(l[i]+r[i])>>1].PB(i);
        }
    }
    for(int i=0;i<q;++i)an[i]=-1;

    for(int lg=0;lg<20;++lg){
        Fenwick f(n);
        for(int i=0;i<q;++i)nquers[i].clear();
        for(int i=0;i<q;++i){
            if(type[i]==1){
                f.upd(L[i],R[i],K[i]);
            }
            for(int id: quers[i]){
                // if(id==2)cout<<i<<' '<<l[id]<<' '<<r[id]<<'\n';
                if(B[id] <= f.quer(A[id])){
                    r[id]=i-1,an[id]=i;
                } else {
                    l[id]=i+1;
                }
                nquers[(l[id]+r[id])>>1].PB(id);
            }
        }
        for(int i=0;i<q;++i)quers[i]=nquers[i];
    }
    for(int i=0;i<q;++i)if(type[i]==3)if(an[i]!=-1)cout<<C[an[i]]<<'\n';else cout<<0<<'\n';


    cerr<<"ok!";
    return 0;
}

• 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