Submission #1241126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241126		hamanp87	Food Court (JOI21_foodcourt)	C++20	24 / 100	74 ms	54980 KiB

foodcourt

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

//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("avx2")
//#pragma GCC target("sse4")

#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
//#define randi uniform_int_distribution<long long>
#define damoon(v) v.resize(unique(all(v))-v.begin())
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//randi dist(0,10000000000000000);

typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,bool> pib;
typedef pair<long long,bool> plb;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef vector<int> veci;
typedef vector<long long> vecl;
typedef vector<bool> vecb;
typedef vector<pii> vecp;
typedef set<int> seti;
typedef set<long long> setl;
typedef set<pii> setp;
typedef map<int,int> mapii;
typedef map<long long,long long> mapll;
typedef map<int,bool> mapib;
typedef map<long long,bool> maplb;

const int mod=1e9+7,neginf=-1e9;
const ll inf=1e15;
const double PI=acos(-1);

struct Segment
{
    int N;
    struct Node
    {
        ll mn,lz;
        Node()
        {
            mn=lz=0;
        }
    };

    vector<Node> t;
    Segment(int n)
    {
        N=n;
        t.resize(4*N);
    }

    void apply(int id,ll v)
    {
        t[id].mn+=v;
        t[id].lz+=v;
    }

    void push(int id)
    {
        if(t[id].lz==0)
            return;

        apply(2*id+0,t[id].lz);
        apply(2*id+1,t[id].lz);
        t[id].lz=0;
    }

    void pull(int id)
    {
        t[id].mn=min(t[2*id+0].mn,t[2*id+1].mn);
    }

    void update(int id,int L,int R,int l,int r,ll v)
    {
        if(r<=L or R<=l)
            return;
        if(l<=L and R<=r)
        {
            apply(id,v);
            return;
        }

        push(id);

        int mid=(L+R)>>1;
        update(2*id+0,L,mid,l,r,v);
        update(2*id+1,mid,R,l,r,v);

        pull(id);
    }

    ll get(int id,int L,int R,int l,int r)
    {
        if(r<=L or R<=l)
            return inf;
        if(l<=L and R<=r)
            return t[id].mn;

        push(id);

        int mid=(L+R)>>1;
        return min(get(2*id+0,L,mid,l,r),get(2*id+1,mid,R,l,r));
    }

    void update(int l,int r,ll v)
    {
        update(1,1,N+1,l,r,v);
    }

    ll get(int l,int r)
    {
        return get(1,1,N+1,l,r);
    }
};

int fposr(Segment &seg,ll x,int id,int L,int R)
{
    if(L+1==R)
        return L;

    seg.push(id);

    int mid=(L+R)>>1;
    if(-seg.t[2*id].mn<x)
        return fposr(seg,x,2*id+1,mid,R);
    else
        return fposr(seg,x,2*id+0,L,mid);
}

int FP(Segment &seg,ll x)
{
    return fposr(seg,x,1,1,seg.N+1);
}

void solve()
{
    int n,m,q;
    cin>>n>>m>>q;
    veci t(q+1),a(q+1),b(q+1);
    vecl c(q+1),k(q+1),bb(q+1);
    vector<veci> opn(n+2),cls(n+2),qls(n+2);
    for(int i=1;i<=q;i++)
    {
        cin>>t[i]>>a[i]>>b[i];
        if(t[i]==1)
        {
            cin>>c[i]>>k[i];
            opn[a[i]].pub(i);
            cls[b[i]].pub(i);
        }
        else if(t[i]==2)
        {
            cin>>k[i];
            opn[a[i]].pub(i);
            cls[b[i]].pub(i);
        }
        else
        {
            qls[a[i]].pub(i);
            bb[i]=b[i];
        }
    }

    Segment Seg0(q),Seg1(q);
    veci ansind(q+1,0);

    for(int i=1;i<=n;i++)
    {
        for(int ind:opn[i])
        {
            if(t[ind]==1)
            {
                Seg0.update(ind,q+1,+k[ind]);
                Seg1.update(ind,q+1,-k[ind]);
            }
            else
            {
                Seg0.update(ind,q+1,-k[ind]);
            }
        }

        for(int qi:qls[i])
        {
            ll cur=Seg0.get(qi,qi+1);
            ll bst=Seg0.get(1,qi+1);
            ll res=cur-min(0LL,bst);
            ll ned=-Seg1.get(qi,qi+1)-res+bb[qi];

            if(bb[qi]>res)
            {
                ansind[qi]=0;
            }
            else
            {
                ansind[qi]=FP(Seg1,ned);
            }
        }

        for(int ind:cls[i])
        {
            if(t[ind]==1)
            {
                Seg0.update(ind,q+1,-k[ind]);
                Seg1.update(ind,q+1,+k[ind]);
            }
            else
            {
                Seg0.update(ind,q+1,+k[ind]);
            }
        }
    }

    for(int i=1;i<=q;i++)
        if(t[i]==3)
            cout<<(ansind[i]?c[ansind[i]]:0)<<"\n";
}

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

    //ifstream fin("in.txt");
    //ofstream fout("out.txt");

    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

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