Submission #890532

#	Time	Username	Problem	Language	Result	Execution time	Memory
890532		LucaIlie	Food Court (JOI21_foodcourt)	C++17	21 / 100	481 ms	9176 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;
 
const int MAX_N = 3e5;
long long v[MAX_N + 1];
 
struct SegTree {
    struct info {
        long long sum, minn;
 
        info operator + ( info &x ) {
            info ans;
 
            ans.minn = min( minn, sum + x.minn );
            ans.sum = sum + x.sum;
 
            return ans;
        }
    };
 
    info lazy[4 * MAX_N];
 
    void propag( int v, int l, int r ) {
        if ( l != r ) {
            lazy[v * 2 + 1] = lazy[v * 2 + 1] + lazy[v];
            lazy[v * 2 + 2] = lazy[v * 2 + 2] + lazy[v];
            lazy[v] = { 0, 0 };
        }
    }
 
    void update( int v, int l, int r, int lu, int ru, int x ) {
        propag( v, l, r );
 
        if ( l > ru || r < lu )
            return;
 
        if ( lu <= l && r <= ru ) {
            info add = { x, min( x, 0 ) };
            lazy[v] = lazy[v] + add;
            propag( v, l, r );
            return;
        }
 
        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, x );
        update( v * 2 + 2, mid + 1, r, lu, ru, x );
    }
 
    long long query( int v, int l, int r, int p ) {
        propag( v, l, r );
 
        if ( l == r )
            return lazy[v].sum - lazy[v].minn;
 
        int mid = (l + r) / 2;
        if ( p <= mid )
            return query( v * 2 + 1, l, mid, p );
        return query( v * 2 + 2, mid + 1, r, p );
    }
} qs;
 
signed main() {
    int n, m, q;
 
    cin >> n >> m >> q;
    while ( q-- ) {
        int type;
 
        cin >> type;
        if ( type == 1 ) {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            qs.update( 0, 1, n, l, r, k );
        } else if ( type == 2 ) {
            int l, r, k;
            cin >> l >> r >> k;
            qs.update( 0, 1, n, l, r, -k );
        } else {
            int p;
            long long x;
            cin >> p >> x;
            long long s = qs.query( 0, 1, n, p );
            cout << (s >= x) << "\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