Submission #891625

#	Time	Username	Problem	Language	Result	Execution time	Memory
891625		LucaIlie	Food Court (JOI21_foodcourt)	C++17	100 / 100	393 ms	51444 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

struct update {
    int c, k;
};


const int MAX_N = 3e5;
const int MAX_Q = 3e5;
int ans[MAX_Q + 1];
update updates[MAX_Q + 2];
long long queries[MAX_Q + 1];
vector<int> updatesByPos[MAX_N + 1], queriesByPos[MAX_N + 1];

struct SegTree {
    struct info {
        long long tot, sum, minn;

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

            ans.tot = tot + x.tot;
            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 k ) {
        propag( v, l, r );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            info add = { max( k, 0 ), k,  min( k, 0 ) };
            lazy[v] = lazy[v] + add;
            propag( v, l, r );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, k );
        update( v * 2 + 2, mid + 1, r, lu, ru, k );
    }

    long long query( int v, int l, int r, int p ) {
        propag( v, l, r );

        if ( l == r )
            return lazy[v].tot - (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;

struct AIB {
    long long aib[MAX_Q + 1];

    void update( int i, int x ) {
        while ( i <= MAX_Q ) {
            aib[i] += x;
            i += (i & -i);
        }
    }

    int firstHigherOrEqual( long long x ) {
        int pos = 0;
        for ( int p = log2( MAX_Q ); p >= 0; p-- ) {
            if ( pos + (1 << p) <= MAX_Q && x - aib[pos + (1 << p)] > 0 ) {
                pos += (1 << p);
                x -= aib[pos];
            }
        }

        return pos + 1;
    }
} us;

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

    int n, m, q;

    cin >> n >> m >> q;
    for ( int t = 1; t <= q; t++ ) {
        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 );
            updates[t] = { c, k };
            updatesByPos[l].push_back( t );
            updatesByPos[r + 1].push_back( -t );
        } 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;
            x += qs.query( 0, 1, n, p );
            queries[t] = x;
            queriesByPos[p].push_back( t );
        }
    }

    for ( int t = 1; t <= q; t++ )
        ans[t] = -1;

    for ( int i = 1; i <= n; i++ ) {
        for ( int t: updatesByPos[i] ) {
            if ( t > 0 )
                us.update( t, updates[t].k );
            else
                us.update( -t, -updates[-t].k );
        }

        for ( int t: queriesByPos[i] ) {
            int j = us.firstHigherOrEqual( queries[t] );
            ans[t] = (j > t ? 0 :updates[j].c );
        }
    }

    for ( int t = 1; t <= q; t++ ) {
        if ( ans[t] != -1 )
            cout << ans[t] << "\n";
    }

    return 0;
}

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