Submission #1241637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241637		hamanp87	Food Court (JOI21_foodcourt)	C++17	24 / 100	65 ms	47296 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 Node
{
    int L,R;
    ll tot;
    pll val;
    Node*Lc,*Rc;

    Node(int l,int r)
    {
        L=l;
        R=r;
        tot=0;
        val=pll(0,0);
        Lc=Rc=nullptr;
    }
};

struct Segment
{
    Node *Root;

    Segment(int L,int R)
    {
        Root=new Node(L,R);
        initialize(Root);
    }

    pll Merge(pll &x,pll &y)
    {
        if(x.S<y.F)
            return pll(x.F+y.F-x.S,y.S);
        return pll(x.F,x.S-y.F+y.S);
    }
    
    void initialize(Node *cur)
    {
        if(cur->L==cur->R)
            return;

        int mid=(cur->L+cur->R)>>1;
        cur->Lc=new Node(cur->L,mid+0);
        cur->Rc=new Node(mid+1,cur->R);

        initialize(cur->Lc);
        initialize(cur->Rc);
    }

    void update(Node *cur,int ind,veci &t,veci &k)
    {
        if(cur->L==cur->R)
        {
            if(cur->val==pll(0,0))
            {
                if(t[ind]==1)
                {
                    cur->tot=k[ind];
                    cur->val=pll(0LL,(ll)k[ind]);
                }
                else
                {
                    cur->tot=0;
                    cur->val=pll((ll)k[ind],0LL);
                }
            }
            else
            {
                cur->tot=0;
                cur->val=pll(0,0);
            }
            return;
        }

        int mid=(cur->L+cur->R)>>1;
        if(ind<=mid)
            update(cur->Lc,ind,t,k);
        else
            update(cur->Rc,ind,t,k);

        cur->tot=cur->Lc->tot+cur->Rc->tot;
        cur->val=Merge(cur->Lc->val,cur->Rc->val);
    }

    ll get1(Node *cur,int rng,ll tmp)
    {
        if(cur->L==cur->R)
            return max(0LL,tmp-cur->val.F)+cur->val.S;

        int mid=(cur->L+cur->R)>>1;
        if(rng<=mid)
            return get1(cur->Lc,rng,tmp);

        ll lnt=max(0LL,tmp-cur->Lc->val.F)+cur->Lc->val.S;
        return get1(cur->Rc,rng,lnt);
    }

    ll get2(Node *cur,int rng)
    {
        if(cur->R<=rng)
            return cur->tot;

        int mid=(cur->L+cur->R)>>1;
        if(rng<=mid)
            return get2(cur->Lc,rng);

        return cur->Lc->tot+get2(cur->Rc,rng);
    }

    ll get3(Node *cur,int rng,ll tar,ll tot)
    {
        if(cur->L==cur->R)
            return cur->L;

        int mid=(cur->L+cur->R)>>1;
        if(mid<rng)
        {
            ll rtot=tot-cur->Lc->tot;
            if(rtot>=tar)
                return get3(cur->Rc,rng,tar,rtot);
            else
                return get3(cur->Lc,rng,tar-rtot,cur->Lc->tot);
        }
        else
        {
            return get3(cur->Lc,rng,tar,tot);
        }
    }
};

void solve()
{
    int n,m,q;
    cin>>n>>m>>q;
    veci t(q+1),l(q+1),r(q+1),c(q+1),k(q+1);
    vector<veci> upds(n+2);
    vector<vecp> qs(n+1);
    for(int i=1;i<=q;i++)
    {
        cin>>t[i];
        if(t[i]==1)
        {
            cin>>l[i]>>r[i]>>c[i]>>k[i];
            upds[l[i]].pub(i);
            upds[r[i]+1].pub(i);
        }
        else if(t[i]==2)
        {
            cin>>l[i]>>r[i]>>k[i];
            upds[l[i]].pub(i);
            upds[r[i]+1].pub(i);
        }
        else
        {
            int a,b;
            cin>>a>>b;
            qs[a].emplace_back(i,b);
        }
    }

    Segment Seg(1,q);

    veci ans(q+1,0);
    for(int d=1;d<=n;d++)
    {
        for(int ind:upds[d])
            Seg.update(Seg.Root,ind,t,k);

        for(auto &qr:qs[d])
        {
            int qi=qr.F;
            int b=qr.S;
            ll res=Seg.get1(Seg.Root,qi,0);

            if(res<b)
                ans[qi]=1;
            else
            {
                ll tot=Seg.get2(Seg.Root,qi);
                ll tar=res-b+1;
                int ind=Seg.get3(Seg.Root,qi,tar,tot);

                ans[qi]=c[ind]+1;
            }
        }
    }

    for(int i=1;i<=q;i++)
        if(ans[i]!=0)
            cout<<ans[i]-1<<"\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