Submission #1198802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198802		Hanksburger	Food Court (JOI21_foodcourt)	C++20	0 / 100	300 ms	60176 KiB

foodcourt

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T[250005], L[250005], R[250005], C[250005], K[250005], ans[250005];
vector<pair<int, int> > queries[250005];
vector<int> updates[250005];
struct node
{
    node *lc, *rc;
    int l, r, tot;
    pair<int, int> val;
    node(int l, int r):lc(0), rc(0), l(l), r(r), tot(0), val({0, 0}) {}
} *root;
pair<int, int> combine(pair<int, int> x, pair<int, int> y)
{
    if (x.second<y.first)
        return {x.first-x.second+y.first, y.second};
    else
        return {x.first, x.second-y.first+y.second};
}
int process(int x, node *i)
{
    return max(0LL, x-i->val.first)+i->val.second;
}
void build(node *i)
{
    if (i->l==i->r)
        return;
    int mid=(i->l+i->r)/2;
    i->lc=new node(i->l, mid);
    i->rc=new node(mid+1, i->r);
    build(i->lc);
    build(i->rc);
}
void upd(node *i, int x)
{
    if (i->l==i->r)
    {
        if (i->val==make_pair(0LL, 0LL))
        {
            if (T[x]==1)
                i->tot=K[x], i->val={0, K[x]};
            else
                i->tot=0, i->val={K[x], 0};
        }
        else
            i->tot=0, i->val={0, 0};
        return;
    }
    int mid=(i->l+i->r)/2;
    if (x<=mid)
        upd(i->lc, x);
    else
        upd(i->rc, x);
    i->tot=i->lc->tot+i->rc->tot;
    i->val=combine(i->lc->val, i->rc->val);
}
int qry1(node *i, int range, int curNum)
{
    if (i->l==i->r)
        return process(curNum, i);
    int mid=(i->l+i->r)/2;
    if (range<=mid)
        return qry1(i->lc, range, curNum);
    return qry1(i->rc, range, process(curNum, i->lc));
}
int qry2(node *i, int range)
{
    if (i->r<=range)
        return i->tot;
    int mid=(i->l+i->r)/2;
    if (range<=mid)
        return qry2(i->lc, range);
    return i->lc->tot+qry2(i->rc, range);
}
int qry3(node *i, int range, int targetNum, int total)
{
    if (i->l==i->r)
        return C[i->l];
    int mid=(i->l+i->r)/2;
    if (mid<range && i->rc->tot>=targetNum)
        return qry3(i->rc, range, targetNum, total-i->lc->tot);
    if (mid<range)
    {
        targetNum-=total-i->lc->tot;
        total=i->lc->tot;
    }
    return qry3(i->lc, range, targetNum, total);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i=1; i<=q; i++)
    {
        cin >> T[i];
        if (T[i]==1)
        {
            cin >> L[i] >> R[i] >> C[i] >> K[i];
            updates[L[i]].push_back(i);
            updates[R[i]+1].push_back(i);
        }
        else if (T[i]==2)
        {
            cin >> L[i] >> R[i] >> K[i];
            updates[L[i]].push_back(i);
            updates[R[i]+1].push_back(i);
        }
        else
        {
            int a, b;
            cin >> a >> b;
            queries[a].push_back({i, b});
        }
    }
    root=new node(1, q);
    build(root);
    for (int i=1; i<=n; i++)
    {
        for (int x:updates[i])
            upd(root, x);
        for (pair<int, int> x:queries[i])
        {
            int res=qry1(root, x.first, 0);
            if (res<x.second)
            {
                ans[x.first]=1;
                continue;
            }
            int res2=qry2(root, x.first);
            ans[x.first]=qry3(root, x.first, res-x.second+1, res2)+1;
        }
    }
    for (int i=1; i<=q; i++)
        if (ans[i])
            cout << ans[i]-1 << '\n';
}

• 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