Submission #397414

#	Time	Username	Problem	Language	Result	Execution time	Memory
397414		phathnv	Food Court (JOI21_foodcourt)	C++11	21 / 100	496 ms	18952 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 25e4 + 7;

struct SegTree{
    int n;
    ll d[N * 4], lazyVal[N * 4], lazyMax[N * 4];
    void init(int _n){
        n = _n;
    }
    void doLazy(int id, int l, int r){
        d[id] += lazyVal[id];
        d[id] = max(d[id], lazyMax[id]);
        if (l < r){
            lazyVal[id << 1] += lazyVal[id];
            lazyMax[id << 1] += lazyVal[id];
            lazyMax[id << 1] = max(lazyMax[id << 1], lazyMax[id]);
            lazyVal[id << 1 | 1] += lazyVal[id];
            lazyMax[id << 1 | 1] += lazyVal[id];
            lazyMax[id << 1 | 1] = max(lazyMax[id << 1 | 1], lazyMax[id]);
        }
        lazyVal[id] = lazyMax[id] = 0;
    }
    void update(int id, int l, int r, int u, int v, int val){
        doLazy(id, l, r);
        if (v < l || r < u)
            return;
        if (u <= l && r <= v){
            lazyVal[id] += val;
            doLazy(id, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
    }
    ll get(int id, int l, int r, int pos){
        doLazy(id, l, r);
        if (pos < l || r < pos)
            return 0;
        if (l == r)
            return d[id];
        int mid = (l + r) >> 1;
        return max(get(id << 1, l, mid, pos), get(id << 1 | 1, mid + 1, r, pos));
    }
    void update(int l, int r, int k){
        update(1, 1, n, l, r, k);
    }
    ll get(int pos){
        return get(1, 1, n, pos);
    }
} st;

int n, m, q;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    assert(m == 1);
    st.init(n);
    while (q--){
        int t;
        cin >> t;
        if (t == 1){
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            st.update(l, r, k);
        } else if (t == 2){
            int l, r, k;
            cin >> l >> r >> k;
            st.update(l, r, -k);
        } else {
            int pos;
            ll val;
            cin >> pos >> val;
            if (st.get(pos) >= val)
                cout << 1 << '\n';
            else
                cout << 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