Submission #888997

#	Time	Username	Problem	Language	Result	Execution time	Memory
888997		LucaIlie	Food Court (JOI21_foodcourt)	C++17	0 / 100	109 ms	2620 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2.5e5;
int v[MAX_N];

struct SegTree {
    struct info {
        int sum, minn;

        info operator + ( info &x ) {
            info ans;

            ans.minn = min( minn, sum + x.sum );
            ans.sum = sum + x.sum;

            return ans;
        }

        void operator += ( info &x ) {
            *this = *this + x;
        }
    };

    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 };
        }
        //printf( "prop %d %d\n %d %d\n", l, r, lazy[v * 2 + 1].sum, lazy[v * 2 + 1].minn );
        //printf( "\n\n" );
    }

    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 ) {
            lazy[v] = { x, 0 };
            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 );
    }

    int 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;

int 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, x;
            cin >> p >> x;
            int 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: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11