Submission #1296563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296563		viyeuquadamdau	Food Court (JOI21_foodcourt)	C++20	0 / 100	1096 ms	30752 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){
            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);
}

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]);
        }
    }

    for(int i=0;i<q;++i){
        if(type[i]==3){
            int l=0,r=i-1;
            while(l<r){
                int m=(l+r)>>1;
                if(chk(m,A[i],B[i]))r=m; // > m
                else l=m+1;
            }
            cout<<C[r]<<'\n';
        }
    }


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

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11