Submission #735720

#	Time	Username	Problem	Language	Result	Execution time	Memory
735720		ismayil	Food Court (JOI21_foodcourt)	C++17	0 / 100	356 ms	14024 KiB

foodcourt

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct segtree{
    vector<int> tree, lazy;
    int size;
    void init(int n){
        size = 1;
        while(size <= n) size *= 2;
        tree.resize(2 * size - 1, 0); lazy.resize(2 * size - 1, 0);
    }
    void propagate(int x, int lx, int rx){
        if(lazy[x] == 0 || lx == rx) return;
        int mx = (lx + rx) / 2;
        tree[2 * x + 1] = max(tree[2 * x + 1] + lazy[x] * (mx - lx + 1), 0LL);
        lazy[2 * x + 1] += lazy[x];
        tree[2 * x + 2] = max(tree[2 * x + 2] + lazy[x] * (rx - mx), 0LL);
        lazy[2 * x + 2] += lazy[x];
        lazy[x] = 0;
    }
    void update(int l, int r, int val, int x, int lx, int rx){
        propagate(x, lx, rx);
        if(r < lx || rx < l) return;
        if(l <= lx && rx <= r){
            tree[x] = max(tree[x] + val, 0LL);
            lazy[x] += val;
            return;
        }
        int mx = (lx + rx) / 2;
        update(l, r, val, 2 * x + 1, lx, mx);
        update(l, r, val, 2 * x + 2, mx + 1, rx);
        tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }
    void update(int l, int r, int val){
        update(l, r, val, 0, 1, size);
    }
    int query(int pos, int x, int lx, int rx){
        propagate(x, lx, rx);
        if(lx == rx) return tree[x];
        int mx = (lx + rx) / 2;
        if(pos <= mx) return query(pos, 2 * x + 1, lx, mx);
        else return query(pos, 2 * x + 2, mx + 1, rx);
    }
    int query(int pos){
        return query(pos, 0, 1, size);
    }
};
void solve(){
    int N, M, Q;
    cin >> N >> M >> Q;
    segtree st;
    st.init(N);
    for(int i = 0; i < Q; i++){
        int type;
        cin >> type;
        if(type == 1){
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            st.update(l, r, k);
        }else if(type == 2){
            int l, r, k;
            cin >> l >> r >> k;
            st.update(l, r, -k);
        }else{
            int a, b;
            cin >> a >> b;
            cout << (st.query(a) >= b ? 1 : 0) << endl;
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("output.txt", "w", stdout);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++){
        //printf("Case #%d: ", i);
        solve();
    }
}

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