Submission #973120

#	Time	Username	Problem	Language	Result	Execution time	Memory
973120		aykhn	Food Court (JOI21_foodcourt)	C++17	100 / 100	513 ms	70508 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct SegTree
{
    int sz = 1;
    vector<array<int, 2>> st;
    void init(int n)
    {
        sz = 1;
        while (sz < n) sz <<= 1;
        st.assign(sz << 1, {0, 0});
    }
    array<int, 2> combine(array<int, 2> x, array<int, 2> y)
    {
        int mn = min(x[0], y[1]);
        x[0] -= mn, y[1] -= mn;
        x[0] += y[0], x[1] += y[1];
        return x;
    }
    void make(int l, int r, int x, int ind, int val, int t)
    {
        if (l + 1 == r)
        {
            st[x][t] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (ind < mid) make(l, mid, 2*x + 1, ind, val, t);
        else make(mid, r, 2*x + 2, ind, val, t);
        st[x] = combine(st[2*x + 1], st[2*x + 2]);
    }
    array<int, 2> get(int l, int r, int x, int lx, int rx)
    {
        if (l >= rx || r <= lx) return {0, 0};
        if (l >= lx && r <= rx) return st[x];
        int mid = (l + r) >> 1;
        return combine(get(l, mid, 2*x + 1, lx, rx), get(mid, r, 2*x + 2, lx, rx));
    }
};

struct SegTreeSUM
{
    int sz = 1;
    vector<int> st;
    void init(int n)
    {
        sz = 1;
        while (sz < n) sz <<= 1;
        st.assign(sz << 1, 0);
    }
    int combine(int x, int y)
    {
        return x + y;
    }
    void make(int l, int r, int x, int ind, int val)
    {
        if (l + 1 == r)
        {
            st[x] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (ind < mid) make(l, mid, 2*x + 1, ind, val);
        else make(mid, r, 2*x + 2, ind, val);
        st[x] = combine(st[2*x + 1], st[2*x + 2]);
    }
    int get(int l, int r, int x, int lx, int rx)
    {
        if (l >= rx || r <= lx) return 0;
        if (l >= lx && r <= rx) return st[x];
        int mid = (l + r) >> 1;
        return combine(get(l, mid, 2*x + 1, lx, rx), get(mid, r, 2*x + 2, lx, rx));
    }
    int findval(int l, int r, int x, int lx, int rx, int val)
    {
        if (l >= rx || r <= lx || st[x] < val) return -1;
        if (l + 1 == r) return l;
        int mid = (l + r) >> 1;
        int A = findval(l, mid, 2*x + 1, lx, rx, val);
        if (A != -1) return A;
        return findval(mid, r, 2*x + 2, lx, rx, val - st[2*x + 1]);
    }
};

const int MXN = 25e4 + 5;

int n, m, Q;
vector<int> q[MXN];
vector<int> add[MXN], del[MXN], here[MXN];
int ans[MXN];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> Q;
    for (int i = 0; i < Q; i++)
    {
        int k;
        cin >> k;
        if (k == 1) k = 4;
        else if (k == 2) k = 3;
        else if (k == 3) k = 2;
        q[i].resize(k);
        for (int &j : q[i]) cin >> j;
        if (k == 4) swap(q[i][2], q[i][3]);
        if (k >= 3)
        {
            add[q[i][0]].push_back(i);
            del[q[i][1] + 1].push_back(i);
        }
        else here[q[i][0]].push_back(i);
    }
    SegTree st;
    SegTreeSUM st1, st2;
    st.init(Q), st1.init(Q), st2.init(Q);
    int sz = st.sz;
    for (int i = 1; i <= n; i++)
    {
        for (int &j : add[i])
        {
            if (q[j].size() == 4) 
            {
                st.make(0, sz, 0, j, q[j][2], 0);
                st1.make(0, sz, 0, j, q[j][2]);
            }
            else 
            {
                st.make(0, sz, 0, j, q[j][2], 1);
                st2.make(0, sz, 0, j, q[j][2]);
            }
        }
        for (int &j : del[i])
        {
            if (q[j].size() == 4) 
            {
                st.make(0, sz, 0, j, 0, 0);
                st1.make(0, sz, 0, j, 0);
            }
            else 
            {
                st.make(0, sz, 0, j, 0, 1);
                st2.make(0, sz, 0, j, 0);
            }
        }
        for (int &j : here[i])
        {
            array<int, 2> x = st.get(0, sz, 0, 0, j);
            int k = st2.get(0, sz, 0, 0, j);
            k -= x[1];
            int ff = k + q[j][1];
            int res = st1.findval(0, sz, 0, 0, j, ff);
            if (res == -1) ans[j] = 0;
            else ans[j] = q[res][3];
        }
    }
    for (int i = 0; i < Q; i++)
    {
        if (q[i].size() == 2) 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