Submission #1280432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280432		denislav	Food Court (JOI21_foodcourt)	C++20	100 / 100	383 ms	65300 KiB

foodcourt

# include <iostream>
# include <vector>
# include <algorithm>
# define all(x) x.begin(),x.end()
# define int long long
using namespace std;

const long long INF=1e18;
const int MAX=3e5+11;

int n,m,q;
struct event
{
    int type,l,r,c,k;
}events[MAX];
int out[MAX];

struct Fenwick
{
    long long tree[MAX];

    void init()
    {
        for(int i=1;i<=n;i++) tree[i]=0;
    }

    void update(int pos, long long x)
    {
        for(int i=pos;i>=1;i-=(i&-i))
        {
            tree[i]+=x;
        }
    }

    void update(int l, int r, long long x)
    {
        update(l-1,-x);
        update(r,x);
    }

    long long query(int pos)
    {
        long long ans=0;
        for(int i=pos;i<=n;i+=(i&-i))
        {
            ans+=tree[i];
        }
        return ans;
    }

}noneg;

struct node
{
    long long sum,mn;

    node friend operator + (node A, node B)
    {
        node res;
        res.sum=A.sum+B.sum;
        res.mn=min(A.mn,A.sum+B.mn);
        return res;
    }
};

struct segtree
{
    node tree[MAX*4];
    node lazy[MAX*4];

    void build(int v=1, int l=1, int r=n)
    {
        lazy[v]={0,0};
        if(l==r)
        {
            tree[v]={0,0};
            return ;
        }

        int mid=(l+r)/2;
        build(v*2,l,mid);
        build(v*2+1,mid+1,r);
        tree[v]=tree[v*2]+tree[v*2+1];
    }

    void push_lazy(int v, int l, int r)
    {
        if(lazy[v].sum==0 and lazy[v].mn==0) return ;

        tree[v]=tree[v]+lazy[v];
        if(l!=r)
        {
            lazy[v*2]=lazy[v*2]+lazy[v];
            lazy[v*2+1]=lazy[v*2+1]+lazy[v];
        }
        lazy[v]={0,0};
    }

    void update(int le, int ri, node nd, int v=1, int l=1, int r=n)
    {
        push_lazy(v,l,r);
        if(ri<l or r<le) return ;
        if(le<=l and r<=ri)
        {
            lazy[v]=lazy[v]+nd;
            push_lazy(v,l,r);
            return ;
        }

        int mid=(l+r)/2;
        update(le,ri,nd,v*2,l,mid);
        update(le,ri,nd,v*2+1,mid+1,r);
        //tree[v]=tree[v*2]+tree[v*2+1];
    }

    node query(int pos, int v=1, int l=1, int r=n)
    {
        push_lazy(v,l,r);
        if(l==r) return tree[v];

        int mid=(l+r)/2;
        if(pos<=mid) return query(pos,v*2,l,mid);
        else return query(pos,v*2+1,mid+1,r);
    }
}tree;

struct question
{
    long long id,k;

    bool friend operator < (question A, question B)
    {
        return A.k<B.k;
    }
};

vector<question> qrs[MAX];

int currentC,currentI;
int answered[MAX];
struct rmq
{
    pair<long long,int> tree[MAX*4];
    long long lazy[MAX*4];

    void build(int v=1, int l=1, int r=n)
    {
        lazy[v]=0;
        if(l==r)
        {
            if(qrs[l].size()==0) tree[v]={INF,l};
            else tree[v]={qrs[l][0].k,l};
            return ;
        }

        int mid=(l+r)/2;
        build(v*2,l,mid);
        build(v*2+1,mid+1,r);
        tree[v]=min(tree[v*2],tree[v*2+1]);
    }

    void push_lazy(int v, int l, int r)
    {
        if(lazy[v]==0) return ;

        tree[v].first+=lazy[v];
        if(l!=r)
        {
            lazy[v*2]+=lazy[v];
            lazy[v*2+1]+=lazy[v];
        }
        lazy[v]=0;
    }

    void update_range(int le, int ri, long long d, int v=1, int l=1, int r=n)
    {
        push_lazy(v,l,r);
        if(ri<l or r<le) return ;
        if(le<=l and r<=ri)
        {
            lazy[v]+=d;
            push_lazy(v,l,r);
            return ;
        }

        int mid=(l+r)/2;
        update_range(le,ri,d,v*2,l,mid);
        update_range(le,ri,d,v*2+1,mid+1,r);
        tree[v]=min(tree[v*2],tree[v*2+1]);
    }

    void update_pos(int pos, int v=1, int l=1, int r=n)
    {
        push_lazy(v,l,r);
        if(l==r)
        {
            int ptr=answered[l];
            if(qrs[l][ptr].id>=currentI) out[qrs[l][ptr].id]=currentC;
            else out[qrs[l][ptr].id]=0;
            //out[qrs[l][ptr].id]=currentC;

            if(ptr==(int)qrs[l].size()-1) tree[v]={INF,0};
            else
            {
                answered[l]++;
                tree[v].first+=qrs[l][ptr+1].k-qrs[l][ptr].k;
            }

            return ;
        }

        int mid=(l+r)/2;
        push_lazy(v*2,l,mid);
        push_lazy(v*2+1,mid+1,r);
        if(pos<=mid) update_pos(pos,v*2,l,mid);
        else update_pos(pos,v*2+1,mid+1,r);
        tree[v]=min(tree[v*2],tree[v*2+1]);
    }

    pair<long long,int> query()
    {
        push_lazy(1,1,n);
        return tree[1];
    }
}rmq;

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m>>q;
    noneg.init();
    tree.build();
    for(int i=1;i<=q;i++)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            int l,r,c,k;
            cin>>l>>r>>c>>k;
            noneg.update(l,r,k);
            tree.update(l,r,{k,k});
            events[i]={type,l,r,c,k};
        }
        else if(type==2)
        {
            int l,r,k;
            cin>>l>>r>>k;
            tree.update(l,r,{-k,-k});
            events[i].type=2;
        }
        else if(type==3)
        {
            long long pos,k;
            cin>>pos>>k;
            node nd=tree.query(pos);
            long long rem=noneg.query(pos)-(nd.sum-nd.mn);
            k+=rem;
            qrs[pos].push_back({i,k});
            events[i].type=3;
            //cout<<i<<":"<<rem<<"\n";
            //cout<<i<<":"<<noneg.query(pos)<<" "<<nd.sum<<" "<<nd.mn<<"\n";
            //cout<<"\n";
        }
    }
    for(int i=1;i<=n;i++) sort(all(qrs[i]));

    rmq.build();
    for(int i=1;i<=q;i++)
    {
        if(events[i].type!=1) continue;

        //cout<<"->"<<i<<endl;

        int l=events[i].l,r=events[i].r,c=events[i].c,k=events[i].k;
        currentI=i;currentC=c;
        rmq.update_range(l,r,-k);
        while(true)
        {
            pair<long long,int> pa=rmq.query();
            //cout<<"->"<<pa.first<<" "<<pa.second<<endl;
            if(pa.first<=0) rmq.update_pos(pa.second);
            else break;
        }
    }

    for(int i=1;i<=q;i++) if(events[i].type==3) cout<<out[i]<<"\n";

    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