Submission #890548

#	Time	Username	Problem	Language	Result	Execution time	Memory
890548		LucaIlie	Food Court (JOI21_foodcourt)	C++17	68 / 100	1066 ms	498980 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

struct aaa {
    int t, c;
    long long k;
};

const int MAX_N = 3e5;
int bucket[MAX_N + 1], leftB[MAX_N + 1], rightB[MAX_N + 1];
long long queueIndexSize[MAX_N + 1], queueBucketSize[MAX_N + 1];
vector<aaa> queueIndex[MAX_N + 1], queueBucket[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() {
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );
    cout.tie( NULL );
    
    int n, m, q;

    cin >> n >> m >> q;

    int bs = sqrt( n );
    for ( int i = 1; i <= n; i++ ) {
        bucket[i] = i / bs;
        queueIndex[i].push_back( { -1, 0, 0 } );
    }
    for ( int b = 0; b * bs <= n; b++ ) {
        leftB[b] = b * bs;
        rightB[b] = min( n, (b + 1) * bs - 1 );
        queueBucket[b].push_back( { -1, 0, 0 } );
    }

    for ( int t = 0; 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 );
            int bl = bucket[l], br = bucket[r];
            if ( bl == br ) {
                for ( int i = l; i <= r; i++ ) {
                    queueIndexSize[i] += k;
                    queueIndex[i].push_back( { t, c, queueIndexSize[i] } );
                }
            } else {
                for ( int i = l; i <= rightB[bl]; i++ ) {
                    queueIndexSize[i] += k;
                    queueIndex[i].push_back( { t, c, queueIndexSize[i] } );
                }
                for ( int i = leftB[br]; i <= r; i++ ) {
                    queueIndexSize[i] += k;
                    queueIndex[i].push_back( { t, c, queueIndexSize[i] } );
                }
                for ( int b = bl + 1; b <= br - 1; b++ ) {
                    queueBucketSize[b] += k;
                    queueBucket[b].push_back( { t, c, queueBucketSize[b] } );
                }
            }
        } 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;
            int b = bucket[p];
            x += queueIndexSize[p] + queueBucketSize[b] - qs.query( 0, 1, n, p );

            int l = -1, r = t;
            while ( r - l > 1 ) {
                int mid = (l + r) / 2;

                int lp = 0, rp = queueIndex[p].size();
                while ( rp - lp > 1 ) {
                    int mp = (lp + rp) / 2;
                    if ( queueIndex[p][mp].t > mid )
                        rp = mp;
                    else
                        lp = mp;
                }

                int lb = 0, rb = queueBucket[b].size();
                while ( rb - lb > 1 ) {
                    int mb = (lb + rb) / 2;
                    if ( queueBucket[b][mb].t > mid )
                        rb = mb;
                    else
                        lb = mb;
                }

                long long k = (queueIndex[p].size() == 0 ? 0 : queueIndex[p][lp].k) + (queueBucket[b].size() == 0 ? 0 : queueBucket[b][lb].k);
                if ( k >= x )
                    r = mid;
                else
                    l = mid;
            }

            if ( r == t )
                cout << "0\n";
            else {
                int lp = 0, rp = queueIndex[p].size();
                while ( rp - lp > 1 ) {
                    int mp = (lp + rp) / 2;
                    if ( queueIndex[p][mp].t > r )
                        rp = mp;
                    else
                        lp = mp;
                }

                int lb = 0, rb = queueBucket[b].size();
                while ( rb - lb > 1 ) {
                    int mb = (lb + rb) / 2;
                    if ( queueBucket[b][mb].t > r )
                        rb = mb;
                    else
                        lb = mb;
                }

                if ( queueIndex[p][lp].t == r )
                    cout << queueIndex[p][lp].c << "\n";
                else if ( queueBucket[b][lb].t == r )
                    cout << queueBucket[b][lb].c << "\n";
                else
                    return 1;
            }
        }
    }

    return 0;
}

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