Submission #600972

#	Time	Username	Problem	Language	Result	Execution time	Memory
600972		AA_Surely	Food Court (JOI21_foodcourt)	C++14	100 / 100	902 ms	80836 KiB

foodcourt

#include <bits/stdc++.h>

#define FOR(i, x, n) for(LL i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(LL i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

#define lc now << 1
#define rc now << 1 | 1

#define T 0
#define L 1
#define R 2
#define C 3
#define K 4
#define A 1
#define B 2

const int N = 3e5 + 5;
const LL INF = 1e18;

int n, m, q;
LL qs[N][5], ans[N];
VLL st[N], ft[N], mq[N];

struct LazySeg {
    PLL tree[N << 2];
    LL lz[N << 2];

    void shift(int now) {
        tree[lc].F += lz[now];
        lz[lc] += lz[now];

        tree[rc].F += lz[now];
        lz[rc] += lz[now];

        lz[now] = 0;
        return;
    }

    PLL init(int now = 1, int ls = 0, int rs = q) {
        if (ls == rs) return tree[now] = {0, ls};
        int mid = (ls + rs) >> 1;
        return tree[now] = min(init(lc, ls, mid), init(rc, mid + 1, rs));
    }

    void add(int lq, int rq, LL val, int now = 1, int ls = 0, int rs = q) {
        if (rq < lq || rq < ls || rs < lq) return;
        if (lq <= ls && rs <= rq) {
            tree[now].F += val;
            lz[now] += val;
            return;
        }

        int mid = (ls + rs) >> 1;
        shift(now);
        add(lq, rq, val, lc, ls, mid);
        add(lq, rq, val, rc, mid + 1, rs);
        
        tree[now] = min(tree[lc], tree[rc]);
        return;
    }

    PLL get(int lq, int rq, int now = 1, int ls = 0, int rs = q) {
        if (rq < lq || rq < ls || rs < lq) return {INF, INF};
        if (lq <= ls && rs <= rq) return tree[now];
        shift(now);
        int mid = (ls + rs) >> 1;
        return min(get(lq, rq, lc, ls, mid), get(lq, rq, rc, mid + 1, rs));
    }
} sum;

struct NormSeg {
    LL tree[N << 2];

    void add(int id, LL val, int now = 1, int ls = 0, int rs = q) {
        if (ls == rs) {
            tree[now] += val;
            return;
        }

        int mid = (ls + rs) >> 1;
        if (id <= mid) add(id, val, lc, ls, mid);
        else add(id, val, rc, mid + 1, rs);

        tree[now] = tree[lc] + tree[rc];
        return;
    }

    LL get(int lq, int rq, int now = 1, int ls = 0, int rs = q) {
        if (rq < lq || rq < ls || rs < lq) return 0;
        if (lq <= ls && rs <= rq) return tree[now];
        int mid = (ls + rs) >> 1;
        return get(lq, rq, lc, ls, mid) + get(lq, rq, rc, mid + 1, rs);
    }

    int rightest(LL val, int now = 1, int ls = 0, int rs = q) {
        //cout << "ls rs " << ls << ' ' << rs << endl;
        if (ls == rs) return ls;
        int mid = (ls + rs) >> 1;
        if (tree[lc] >= val) return rightest(val, lc, ls, mid);
        return rightest(val - tree[lc], rc, mid + 1, rs);
    }
} pos, neg;

void init() {
    cin >> n >> m >> q;
    FOR(i, 1, q + 1) {
        cin >> qs[i][T];
        if (qs[i][T] == 1) {
            cin >> qs[i][L] >> qs[i][R] >> qs[i][C] >> qs[i][K];
            st[ qs[i][L] ].PB(i);
            ft[ qs[i][R] ].PB(i);
        }

        if (qs[i][T] == 2) {
            cin >> qs[i][L] >> qs[i][R] >> qs[i][K];
            st[ qs[i][L] ].PB(i);
            ft[ qs[i][R] ].PB(i);
        }

        if (qs[i][T] == 3) {
            cin >> qs[i][A] >> qs[i][B];
            mq[ qs[i][A] ].PB(i);
        }
    }
}

int main() {
    IOS;

    init();

    sum.init();

    FOR(i, 1, n + 1) {
        for(const int &on : st[i]) {
            if (qs[on][T] == 1) {
                sum.add(on, q, qs[on][K]);
                pos.add(on, qs[on][K]);
            }

            else {
                sum.add(on, q, -qs[on][K]);
                neg.add(on, qs[on][K]);
            }
        }

        for(const int &on : mq[i]) {
            LL pl = sum.get(0, on).S;
            LL ppl = pos.get(0, pl) + neg.get(pl + 1, on - 1) + qs[on][B];
            
            if (pos.get(0, on) < ppl) ans[on] = 0;
            else ans[on] = qs[pos.rightest(ppl)][C];
        }

        for(const int &on : ft[i]) {
            if (qs[on][T] == 1) {
                sum.add(on, q, -qs[on][K]);
                pos.add(on, -qs[on][K]);
            }

            else {
                sum.add(on, q, qs[on][K]);
                neg.add(on, -qs[on][K]);
            }
        }
    }

    FOR(i, 1, q + 1) if (qs[i][T] == 3) 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