Submission #1261119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261119		chikien2009	Food Court (JOI21_foodcourt)	C++20	68 / 100	72 ms	25416 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct NODE
{
    long long val = 0, exp = 0;
} t1, t2;

struct SEGMENT_TREE
{
    NODE tree[1000000];
    inline void Update(int ind, int l, int r, int x, int v)
    {
        if (r < x || x < l)
        {
            return;
        }
        if (l == r)
        {
            tree[ind].val = v;
            tree[ind].exp = min(0, v);
            return;
        }
        int m = (l + r) >> 1;
        Update(ind << 1, l, m, x, v);
        Update(ind << 1 | 1, m + 1, r, x, v);
        tree[ind].val = tree[ind << 1].val + tree[ind << 1 | 1].val;
        tree[ind].exp = min(tree[ind << 1].exp, tree[ind << 1].val + tree[ind << 1 | 1].exp);
    }
    inline NODE Get(int ind, int l, int r, int x)
    {
        if (x < l)
        {
            return NODE();
        }
        if (r <= x)
        {
            return tree[ind];
        }
        int m = (l + r) >> 1;
        NODE lc = Get(ind << 1, l, m, x);
        NODE rc = Get(ind << 1 | 1, m + 1, r, x);
        return {lc.val + rc.val, min(lc.exp, lc.val + rc.exp)};
    }
    inline int GetPos(int ind, int l, int r, long long v)
    {
        if (l == r)
        {
            return l;
        }
        int m = (l + r) >> 1;
        if (v <= tree[ind << 1].val)
        {
            return GetPos(ind << 1, l, m, v);
        }
        return GetPos(ind << 1 | 1, m + 1, r, v - tree[ind << 1].val);
    }
} st1, st2;

int n, m, q, a, c[250000], d;
long long b;
vector<pair<int, int>> add[250000], del[250000], res;
vector<pair<int, long long>> ask[250000];

int main()
{
    setup();

    cin >> n >> m >> q;
    for (int i = 0; i < q; ++i)
    {
        cin >> a;
        if (a == 1)
        {
            cin >> a >> b >> c[i] >> d;
            add[a - 1].push_back({i, d});
            if (b < m)
            {
                add[b].push_back({i, 0});
            }
        }
        else if (a == 2)
        {
            cin >> a >> b >> d;
            del[a - 1].push_back({i, -d});
            if (b < m)
            {
                del[b].push_back({i, 0});
            }
        }
        else
        {
            cin >> a >> b;
            ask[a - 1].push_back({i, b});
        }
    }
    for (int i = 0; i < m; ++i)
    {
        for (auto &j : add[i])
        {
            st1.Update(1, 0, q - 1, j.first, j.second);
            st2.Update(1, 0, q - 1, j.first, j.second);
        }
        for (auto &j : del[i])
        {
            st1.Update(1, 0, q - 1, j.first, j.second);
        }
        for (auto &j : ask[i])
        {
            t1 = st1.Get(1, 0, q - 1, j.first);
            t2 = st2.Get(1, 0, q - 1, j.first);
            b = t2.val - t1.val + t1.exp + j.second;
            if (b > t2.val)
            {
                res.push_back({j.first, 0});
            }
            else
            {
                res.push_back({j.first, c[st2.GetPos(1, 0, q - 1, b)]});
            }
        }
    }
    sort(res.begin(), res.end());
    for (auto & i : res)
    {
        cout << i.second << "\n";
    }
    return 0;
}

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