Submission #1095552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095552		cpismylifeOwO	Food Court (JOI21_foodcourt)	C++17	100 / 100	436 ms	60756 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 3e5 + 5;
const int MaxLog = 20;

struct Query
{
    int type;
    int l, r, c, a;
    long long k, b;

    Query() = default;

    Query(int _l, int _r, long long _k, int _c)
    {
        type = 1;
        l = _l;
        r = _r;
        k = _k;
        c = _c;
    }

    Query(int _l, int _r, long long _k)
    {
        type = 2;
        l = _l;
        r = _r;
        k = _k;
    }

    Query(int _a, long long _b)
    {
        type = 3;
        a = _a;
        b = _b;
    }
};

int n, m, q;
Query query[MaxN];

void Inp()
{
    cin >> n >> m >> q;
    for (int x = 1; x <= q; x++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int l, r, c;
            long long k;
            cin >> l >> r >> c >> k;
            query[x] = Query(l, r, k, c);
        }
        else if (type == 2)
        {
            int l, r;
            long long k;
            cin >> l >> r >> k;
            query[x] = Query(l, r, k);
        }
        else
        {
            int a;
            long long b;
            cin >> a >> b;
            query[x] = Query(a, b);
        }
    }
}

long long SegTree[4 * MaxN];
long long Lazy[4 * MaxN];

void Fix(int id, int l, int r)
{
    if (Lazy[id] == 0)
    {
        return;
    }
    SegTree[id] += Lazy[id];
    if (l != r)
    {
        Lazy[id << 1] += Lazy[id];
        Lazy[id << 1 | 1] += Lazy[id];
    }
    Lazy[id] = 0;
}

void Update(int id, int l, int r, int i, int j, long long v)
{
    Fix(id, l, r);
    if (j < l || r < i)
    {
        return;
    }
    if (i <= l && r <= j)
    {
        Lazy[id] += v;
        Fix(id, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    Update(id << 1, l, mid, i, j, v);
    Update(id << 1 | 1, mid + 1, r, i, j, v);
    SegTree[id] = min(SegTree[id << 1], SegTree[id << 1 | 1]);
}

long long Get(int id, int l, int r, int i, int j)
{
    Fix(id, l, r);
    if (j < l || r < i)
    {
        return 1e18;
    }
    if (i <= l && r <= j)
    {
        return SegTree[id];
    }
    int mid = (l + r) >> 1;
    return min(Get(id << 1, l, mid, i, j), Get(id << 1 | 1, mid + 1, r, i, j));
}

long long Fenwick1[MaxN];
long long Fenwick2[MaxN];

void UpdateBIT1(int u, long long v)
{
    int idx = u;
    while (idx <= q)
    {
        Fenwick1[idx] += v;
        idx += (idx & (-idx));
    }
}

void UpdateBIT2(int u, long long v)
{
    int idx = u;
    while (idx <= q)
    {
        Fenwick2[idx] += v;
        idx += (idx & (-idx));
    }
}

int BSearchBIT1(long long p)
{
    int pos = 0;
    long long sum = 0;
    for (int x = MaxLog - 1; x >= 0; x--)
    {
        if (pos + (1 << x) <= q && sum + Fenwick1[pos + (1 << x)] < p)
        {
            pos += (1 << x);
            sum += Fenwick1[pos];
        }
    }
    return pos + 1;
}

long long GetBIT2(int u)
{
    int idx = u;
    long long res = 0;
    while (idx > 0)
    {
        res += Fenwick2[idx];
        idx -= (idx & (-idx));
    }
    return res;
}

vector<int> markin[MaxN];
vector<int> markout[MaxN];
vector<int> markque[MaxN];
int res[MaxN];

void Exc()
{
    for (int x = 1; x <= q; x++)
    {
        if (query[x].type == 3)
        {
            markque[query[x].a].push_back(x);
        }
        else
        {
            markin[query[x].l].push_back(x);
            markout[query[x].r + 1].push_back(x);
        }
    }
    for (int x = 1; x <= n; x++)
    {
        for (int y : markin[x])
        {
            if (query[y].type == 1)
            {
                Update(1, 1, q, y, q, query[y].k);
                UpdateBIT1(y, query[y].k);
            }
            else
            {
                Update(1, 1, q, y, q, -query[y].k);
                UpdateBIT2(y, query[y].k);
            }
        }
        for (int y : markout[x])
        {
            if (query[y].type == 1)
            {
                Update(1, 1, q, y, q, -query[y].k);
                UpdateBIT1(y, -query[y].k);
            }
            else
            {
                Update(1, 1, q, y, q, query[y].k);
                UpdateBIT2(y, -query[y].k);
            }
        }
        for (int y : markque[x])
        {
            long long p = Get(1, 1, q, 1, y);
            if (p < 0)
            {
                p = abs(p);
            }
            else
            {
                p = 0;
            }
            p = GetBIT2(y) - p;
            int t = BSearchBIT1(query[y].b + p);
            if (t > y)
            {
                res[y] = 0;
            }
            else
            {
                assert(query[t].type == 1);
                res[y] = query[t].c;
            }
        }
    }
    for (int x = 1; x <= q; x++)
    {
        if (query[x].type == 3)
        {
            cout << res[x] << "\n";
        }
    }
}

int main()
{
    //freopen("C.INP", "r", stdin);
    //freopen("C.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

• 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