Submission #891187

#	Time	Username	Problem	Language	Result	Execution time	Memory
891187		LucaIlie	Food Court (JOI21_foodcourt)	C++17	68 / 100	1065 ms	88068 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 3e5;
int group[MAX_N];

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];
    long long size[4 * MAX_N];
    vector<aaa> q[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 init( int v, int l, int r ) {
        q[v].push_back( { -1, 0, 0 } );
        if ( l == r )
            return;
        int mid = (l + r) / 2;
        init( v * 2 + 1, l, mid );
        init( v * 2 + 2, mid + 1, r );
    }
    void update( int v, int l, int r, int lu, int ru, int k, int c, int t ) {
        propag( v, l, r );

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

        if ( lu <= l && r <= ru ) {
            if ( k > 0 ) {
                size[v] += k;
                q[v].push_back( { t, c, size[v] } );
            }
            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, c, t );
        update( v * 2 + 2, mid + 1, r, lu, ru, k, c, t );
    }

    vector<int> ans;
    long long query( int v, int l, int r, int p ) {
        if ( v == 0 )
            ans.clear();
        ans.push_back( v );
        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;

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

    int n, m, q;

    cin >> n >> m >> q;
    qs.init( 0, 1, n );
    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, c, t );
            group[t] = c;
        } else if ( type == 2 ) {
            int l, r, k;
            cin >> l >> r >> k;
            qs.update( 0, 1, n, l, r, -k, 0, t );
        } else {
            int p;
            long long x;
            cin >> p >> x;
            x += qs.query( 0, 1, n, p );
            vector<int> vert = qs.ans;

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

                long long k = 0;
                for ( int v: vert ) {
                    int lp = 0, rp = qs.q[v].size();
                    while ( rp - lp > 1 ) {
                        int mp = (lp + rp) / 2;
                        if ( qs.q[v][mp].t > mid )
                            rp = mp;
                        else
                            lp = mp;
                    }
                    k += qs.q[v][lp].k;
                }

                if ( k >= x )
                    r = mid;
                else
                    l = mid;
            }

            cout << group[r] << "\n";
        }
    }

    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