Submission #1141588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141588		omsincoconut	Food Court (JOI21_foodcourt)	C++20	21 / 100	299 ms	31920 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const int MAXN = 250005, MAXT = 4*MAXN+5;\
const pll NULLPAIR = make_pair(0LL, 0LL);

pll op1(pll a, pll b) {
    // The pairs are (-, +)
    if (a.second >= b.first) return make_pair(a.first, a.second-b.first+b.second);
    else return make_pair(a.first-a.second+b.first, b.second);
}

struct max0_segtree{
    pll tree[MAXT];
    pll lz[MAXT];

    void init() {
        fill(tree, tree+MAXT, NULLPAIR);
        fill(lz, lz+MAXT, NULLPAIR);
    }

    void push(int v, int l, int r) {
        tree[v] = op1(tree[v], lz[v]);
        if (l < r) {
            lz[v<<1] = op1(lz[v<<1], lz[v]);
            lz[(v<<1)+1] = op1(lz[(v<<1)+1], lz[v]);
        }
        lz[v] = NULLPAIR;
    }

    void update(int l, int r, ll x, int tl = 1, int tr = MAXN, int v = 1) {
        push(v, tl, tr);
        if (tr < l || r < tl) return;
        if (l <= tl && tr <= r) {
            if (x >= 0) lz[v] = op1(lz[v], make_pair(0LL, x));
            else lz[v] = op1(lz[v], make_pair(-x, 0LL));
            return;
        }

        int mid = (tl+tr)>>1;
        update(l, r, x, tl, mid, v<<1);
        update(l, r, x, mid+1, tr, (v<<1)+1);
    }

    ll query(int p, int l = 1, int r = MAXN, int v = 1) {
        push(v, l, r);
        if (l == r) return tree[v].second;

        int mid = (l+r)>>1;
        if (p <= mid) return query(p, l, mid, v<<1);
        else return query(p, mid+1, r, (v<<1)+1);
    }
} sub4;

int N, M, Q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    sub4.init();

    cin >> N >> M >> Q;
    
    while (Q--) {
        int T;
        cin >> T;

        if (T == 1) {
            int L, R, C;
            ll K;
            cin >> L >> R >> C >> K;
            sub4.update(L, R, K);
        } else if (T == 2) {
            int L, R;
            ll K;
            cin >> L >> R >> K;
            sub4.update(L, R, -K);
        } else {
            int A;
            ll B;
            cin >> A >> B;
            cout << (sub4.query(A) >= B ? 1 : 0) << "\n";
        }
    }

    return 0;
}

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