Submission #932397

#	Time	Username	Problem	Language	Result	Execution time	Memory
932397		andrei_boaca	Food Court (JOI21_foodcourt)	C++17	0 / 100	458 ms	62832 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll INF=1e17;
ll n,m,q;
struct date
{
    ll tip,l,r,k,c;
} v[250005];
vector<int> ev[250005];
bool comp(int a, int b)
{
    return v[a].tip<v[b].tip;
}
pll arbmin[4*250005];
ll arbmax[4*250005],arbsum[4*250005];
ll topropmin[4*250005],topropmax[4*250005],topropsum[4*250005];
ll sol[250005];
void buildmin(ll nod,ll st,ll dr)
{
    arbmin[nod]={0,st};
    if(st==dr)
        return;
    ll mij=(st+dr)/2;
    buildmin(nod*2,st,mij);
    buildmin(nod*2+1,mij+1,dr);
}
void propmin(ll nod)
{
    ll val=topropmin[nod];
    arbmin[nod*2].first+=val;
    arbmin[nod*2+1].first+=val;
    topropmin[nod*2]+=val;
    topropmin[nod*2+1]=val;
}
void updatemin(ll nod,ll st,ll dr,ll a,ll b,ll val)
{
    if(st<dr)
        propmin(nod);
    topropmin[nod]=0;
    if(st>=a&&dr<=b)
    {
        arbmin[nod].first+=val;
        topropmin[nod]+=val;
        return;
    }
    ll mij=(st+dr)/2;
    if(a<=mij)
        updatemin(nod*2,st,mij,a,b,val);
    if(b>mij)
        updatemin(nod*2+1,mij+1,dr,a,b,val);
    arbmin[nod]=min(arbmin[nod*2],arbmin[nod*2+1]);
}
pll querymin(ll nod,ll st,ll dr,ll a,ll b)
{
    if(st<dr)
        propmin(nod);
    topropmin[nod]=0;
    if(st>=a&&dr<=b)
        return arbmin[nod];
    pll rez={INF,INF};
    ll mij=(st+dr)/2;
    if(a<=mij)
        rez=min(rez,querymin(nod*2,st,mij,a,b));
    if(b>mij)
        rez=min(rez,querymin(nod*2+1,mij+1,dr,a,b));
    return rez;
}
void propmax(ll nod)
{
    ll val=topropmax[nod];
    arbmax[nod*2]+=val;
    arbmax[nod*2+1]+=val;
    topropmax[nod*2]+=val;
    topropmax[nod*2+1]+=val;
}
void updatemax(ll nod,ll st,ll dr,ll a,ll b,ll val)
{
    if(st<dr)
        propmax(nod);
    topropmax[nod]=0;
    if(st>=a&&dr<=b)
    {
        arbmax[nod]+=val;
        topropmax[nod]+=val;
        return;
    }
    ll mij=(st+dr)/2;
    if(a<=mij)
        updatemax(nod*2,st,mij,a,b,val);
    if(b>mij)
        updatemax(nod*2+1,mij+1,dr,a,b,val);
    arbmax[nod]=max(arbmax[nod*2],arbmax[nod*2+1]);
}
ll querymax(ll nod,ll st,ll dr,ll a,ll b)
{
    if(st<dr)
        propmax(nod);
    topropmax[nod]=0;
    if(st>=a&&dr<=b)
        return arbmax[nod];
    ll rez=0;
    ll mij=(st+dr)/2;
    if(a<=mij)
        rez=max(rez,querymax(nod*2,st,mij,a,b));
    if(b>mij)
        rez=max(rez,querymax(nod*2+1,mij+1,dr,a,b));
    return rez;
}
ll getfirst(ll nod,ll st,ll dr,ll val)
{
    if(st<dr)
        propmax(nod);
    topropmax[nod]=0;
    if(arbmax[nod]<val)
        return INF;
    if(st==dr)
        return st;
    ll mij=(st+dr)/2;
    if(arbmax[nod*2]>=val)
        return getfirst(nod*2,st,mij,val);
    return getfirst(nod*2+1,mij+1,dr,val);
}
void updatesum(ll nod,ll st,ll dr,ll poz,ll val)
{
    if(st==dr)
    {
        arbsum[nod]+=val;
        return;
    }
    ll mij=(st+dr)/2;
    if(poz<=mij)
        updatesum(nod*2,st,mij,poz,val);
    else
        updatesum(nod*2+1,mij+1,dr,poz,val);
    arbsum[nod]=arbsum[nod*2]+arbsum[nod*2+1];
}
ll querysum(ll nod,ll st,ll dr,ll a,ll b)
{
    if(st>=a&&dr<=b)
        return arbsum[nod];
    ll mij=(st+dr)/2;
    ll rez=0;
    if(a<=mij)
        rez+=querysum(nod*2,st,mij,a,b);
    if(b>mij)
        rez+=querysum(nod*2+1,mij+1,dr,a,b);
    return rez;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>v[i].tip;
        if(v[i].tip==1)
        {
            cin>>v[i].l>>v[i].r>>v[i].c>>v[i].k;
            ev[v[i].l].push_back(i);
            ev[v[i].r+1].push_back(i);
        }
        if(v[i].tip==2)
        {
            cin>>v[i].l>>v[i].r>>v[i].k;
            ev[v[i].l].push_back(i);
            ev[v[i].r+1].push_back(i);
        }
        if(v[i].tip==3)
        {
            cin>>v[i].l>>v[i].k;
            ev[v[i].l].push_back(i);
        }
    }
    buildmin(1,1,q);
    for(int z=1;z<=n;z++)
        if(!ev[z].empty())
        {
            sort(ev[z].begin(),ev[z].end(),comp);
            for(int i:ev[z])
            {
                if(v[i].tip==1)
                {
                    if(z==v[i].l)
                    {
                        updatemin(1,1,q,i,q,v[i].k);
                        updatemax(1,1,q,i,q,v[i].k);
                    }
                    else
                    {
                        updatemin(1,1,q,i,q,-v[i].k);
                        updatemax(1,1,q,i,q,-v[i].k);
                    }
                }
                if(v[i].tip==2)
                {
                    if(z==v[i].l)
                    {
                        updatemin(1,1,q,i,q,-v[i].k);
                        updatesum(1,1,q,i,-v[i].k);
                    }
                    else
                    {
                        updatemin(1,1,q,i,q,v[i].k);
                        updatesum(1,1,q,i,v[i].k);
                    }
                }
                if(v[i].tip==3)
                {
                    ll b=v[i].k;
                    pll p=querymin(1,1,q,1,i);
                    ll st=1;
                    ll dr=i;
                    if(p.first<0)
                        st=p.second+1;
                    if(st>dr)
                    {
                        sol[i]=0;
                        continue;
                    }
                    ll x=querysum(1,1,q,st,dr);
                    b-=x;
                    if(st-1>0)
                        b+=querymax(1,1,q,1,st-1);
                    ll poz=getfirst(1,1,q,b);
                    if(poz<=dr)
                        sol[i]=v[poz].c;
                }
            }
        }
    for(int i=1;i<=q;i++)
        if(v[i].tip==3)
            cout<<sol[i]<<'\n';
    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