제출 #1265320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265320		tvgk	푸드 코트 (JOI21_foodcourt)	C++20	100 / 100	300 ms	40412 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 25e4 + 7;

struct node
{
    ll sum, pen, inc;
};

int n, m, q, c[mxN];
ll ans[mxN];
node tree[mxN * 4];
vector<ii> vc[mxN], querry[mxN];

node Merge(node u, node v)
{
    node res;
    res.sum = u.sum + v.sum;
    res.pen = min(u.pen, u.sum + v.pen);
    res.inc = u.inc + v.inc;
    return res;
}

void Upd(int vt, int val, int j = 1, int l = 1, int r = q)
{
    if (l > vt || vt > r)
        return;

    if (l == r)
    {
        tree[j].sum = val;
        tree[j].pen = min(0, val);
        tree[j].inc = max(0, val);
        return;
    }

    int mid = (l + r) / 2;
    Upd(vt, val, j * 2, l, mid);
    Upd(vt, val, j * 2 + 1, mid + 1, r);
    tree[j] = Merge(tree[j * 2], tree[j * 2 + 1]);
}

node Get(int vt, int j = 1, int l = 1, int r = q)
{
    if (vt < l)
        return node();

    if (r <= vt)
        return tree[j];

    int mid = (l + r) / 2;
    return Merge(Get(vt, j * 2, l, mid), Get(vt, j * 2 + 1, mid + 1, r));
}

int Walk(int vt, ll& tmp, int j = 1, int l = 1, int r = q)
{
    if (vt < l || tmp <= 0)
        return 0;

    if (tree[j].inc < tmp && r <= vt)
    {
        tmp -= tree[j].inc;
        return 0;
    }

    if (l == r)
    {
        tmp = 0;
        return c[l];
    }

    int mid = (l + r) / 2;
    int v = Walk(vt, tmp, j * 2 + 1, mid + 1, r);
    int u = Walk(vt, tmp, j * 2, l, mid);
    return max(u, v);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++)
    {
        int tt;
        cin >> tt;

        if (tt == 1)
        {
            int l, r, num;
            cin >> l >> r >> c[i] >> num;
            vc[l].push_back({i, num});
            vc[r + 1].push_back({i, 0});
        }
        else if (tt == 2)
        {
            int l, r, num;
            cin >> l >> r >> num;
            vc[l].push_back({i, -num});
            vc[r + 1].push_back({i, 0});
        }
        else
        {
            ll vt, stt;
            cin >> vt >> stt;
            querry[vt].push_back({i, stt});
        }
        ans[i] = -1;
    }

    for (int i = 1; i <= n; i++)
    {
        for (ii j : vc[i])
            Upd(j.fi, j.se);

        for (ii j : querry[i])
        {
            node tmp = Get(j.fi);
            ll del = tmp.sum - tmp.pen - j.se + 1;
            ans[j.fi] = Walk(j.fi, del);
        }
    }

    for (int i = 1; i <= q; i++)
        if (ans[i] >= 0)
            cout << ans[i] << '\n';
}

• 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