oj.uz

Submission #890544

# Submission time Handle Problem Language Result Execution time Memory
890544 2023-12-21T12:45:06 Z LucaIlie Food Court (JOI21_foodcourt) C++17
14 / 100
 747 ms 524288 KB 
#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() {
    int n, m, q;

    cin >> n >> m >> q;

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

    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 ( queueBucket[b].size() == 0 || (queueIndex[p].size() > 0 && queueIndex[p][lp].t > queueBucket[b][rb].t) )
                    cout << queueIndex[p][lp].c << "\n";
                else
                    cout << queueBucket[b][lb].c << "\n";
            }
        }
    }

    return 0;
}

Compilation message

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:91:17: warning: unused variable 'bl' [-Wunused-variable]
   91 |             int bl = bucket[l], br = bucket[r];
      |                 ^~
foodcourt.cpp:91:33: warning: unused variable 'br' [-Wunused-variable]
   91 |             int bl = bucket[l], br = bucket[r];
      |                                 ^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22616 KB Output is correct
2 Correct 17 ms 28252 KB Output is correct
3 Correct 19 ms 30092 KB Output is correct
4 Correct 29 ms 40792 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 5 ms 16864 KB Output is correct
7 Correct 24 ms 34140 KB Output is correct
8 Correct 22 ms 33860 KB Output is correct
9 Correct 23 ms 33884 KB Output is correct
10 Correct 23 ms 34908 KB Output is correct
11 Correct 23 ms 35392 KB Output is correct
12 Correct 23 ms 34248 KB Output is correct
13 Correct 30 ms 42588 KB Output is correct
14 Correct 37 ms 47700 KB Output is correct
15 Correct 23 ms 32348 KB Output is correct
16 Correct 36 ms 47440 KB Output is correct
17 Correct 14 ms 25948 KB Output is correct
18 Correct 20 ms 30772 KB Output is correct
19 Correct 6 ms 17244 KB Output is correct
20 Correct 6 ms 17248 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22616 KB Output is correct
2 Correct 17 ms 28252 KB Output is correct
3 Correct 19 ms 30092 KB Output is correct
4 Correct 29 ms 40792 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 5 ms 16864 KB Output is correct
7 Correct 24 ms 34140 KB Output is correct
8 Correct 22 ms 33860 KB Output is correct
9 Correct 23 ms 33884 KB Output is correct
10 Correct 23 ms 34908 KB Output is correct
11 Correct 23 ms 35392 KB Output is correct
12 Correct 23 ms 34248 KB Output is correct
13 Correct 30 ms 42588 KB Output is correct
14 Correct 37 ms 47700 KB Output is correct
15 Correct 23 ms 32348 KB Output is correct
16 Correct 36 ms 47440 KB Output is correct
17 Correct 14 ms 25948 KB Output is correct
18 Correct 20 ms 30772 KB Output is correct
19 Correct 6 ms 17244 KB Output is correct
20 Correct 6 ms 17248 KB Output is correct
21 Correct 16 ms 27228 KB Output is correct
22 Correct 17 ms 28416 KB Output is correct
23 Correct 21 ms 32604 KB Output is correct
24 Correct 28 ms 40528 KB Output is correct
25 Correct 5 ms 16732 KB Output is correct
26 Correct 5 ms 16732 KB Output is correct
27 Correct 22 ms 31620 KB Output is correct
28 Correct 24 ms 34652 KB Output is correct
29 Correct 23 ms 34652 KB Output is correct
30 Correct 23 ms 34424 KB Output is correct
31 Correct 27 ms 31064 KB Output is correct
32 Correct 22 ms 31060 KB Output is correct
33 Correct 29 ms 41296 KB Output is correct
34 Correct 38 ms 47964 KB Output is correct
35 Correct 29 ms 39516 KB Output is correct
36 Correct 35 ms 47192 KB Output is correct
37 Correct 5 ms 16984 KB Output is correct
38 Correct 6 ms 17244 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 22868 KB Output is correct
2 Correct 109 ms 24656 KB Output is correct
3 Correct 120 ms 25684 KB Output is correct
4 Correct 122 ms 25680 KB Output is correct
5 Correct 171 ms 28756 KB Output is correct
6 Correct 130 ms 28540 KB Output is correct
7 Correct 85 ms 17360 KB Output is correct
8 Correct 83 ms 17760 KB Output is correct
9 Correct 103 ms 23380 KB Output is correct
10 Correct 108 ms 23380 KB Output is correct
11 Correct 118 ms 23232 KB Output is correct
12 Correct 114 ms 23224 KB Output is correct
13 Correct 98 ms 24916 KB Output is correct
14 Correct 112 ms 25916 KB Output is correct
15 Correct 138 ms 28248 KB Output is correct
16 Correct 126 ms 28464 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 747 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22616 KB Output is correct
2 Correct 17 ms 28252 KB Output is correct
3 Correct 19 ms 30092 KB Output is correct
4 Correct 29 ms 40792 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 5 ms 16864 KB Output is correct
7 Correct 24 ms 34140 KB Output is correct
8 Correct 22 ms 33860 KB Output is correct
9 Correct 23 ms 33884 KB Output is correct
10 Correct 23 ms 34908 KB Output is correct
11 Correct 23 ms 35392 KB Output is correct
12 Correct 23 ms 34248 KB Output is correct
13 Correct 30 ms 42588 KB Output is correct
14 Correct 37 ms 47700 KB Output is correct
15 Correct 23 ms 32348 KB Output is correct
16 Correct 36 ms 47440 KB Output is correct
17 Correct 14 ms 25948 KB Output is correct
18 Correct 20 ms 30772 KB Output is correct
19 Correct 6 ms 17244 KB Output is correct
20 Correct 6 ms 17248 KB Output is correct
21 Correct 118 ms 22868 KB Output is correct
22 Correct 109 ms 24656 KB Output is correct
23 Correct 120 ms 25684 KB Output is correct
24 Correct 122 ms 25680 KB Output is correct
25 Correct 171 ms 28756 KB Output is correct
26 Correct 130 ms 28540 KB Output is correct
27 Correct 85 ms 17360 KB Output is correct
28 Correct 83 ms 17760 KB Output is correct
29 Correct 103 ms 23380 KB Output is correct
30 Correct 108 ms 23380 KB Output is correct
31 Correct 118 ms 23232 KB Output is correct
32 Correct 114 ms 23224 KB Output is correct
33 Correct 98 ms 24916 KB Output is correct
34 Correct 112 ms 25916 KB Output is correct
35 Correct 138 ms 28248 KB Output is correct
36 Correct 126 ms 28464 KB Output is correct
37 Runtime error 606 ms 524288 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 610 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22616 KB Output is correct
2 Correct 17 ms 28252 KB Output is correct
3 Correct 19 ms 30092 KB Output is correct
4 Correct 29 ms 40792 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 5 ms 16864 KB Output is correct
7 Correct 24 ms 34140 KB Output is correct
8 Correct 22 ms 33860 KB Output is correct
9 Correct 23 ms 33884 KB Output is correct
10 Correct 23 ms 34908 KB Output is correct
11 Correct 23 ms 35392 KB Output is correct
12 Correct 23 ms 34248 KB Output is correct
13 Correct 30 ms 42588 KB Output is correct
14 Correct 37 ms 47700 KB Output is correct
15 Correct 23 ms 32348 KB Output is correct
16 Correct 36 ms 47440 KB Output is correct
17 Correct 14 ms 25948 KB Output is correct
18 Correct 20 ms 30772 KB Output is correct
19 Correct 6 ms 17244 KB Output is correct
20 Correct 6 ms 17248 KB Output is correct
21 Correct 16 ms 27228 KB Output is correct
22 Correct 17 ms 28416 KB Output is correct
23 Correct 21 ms 32604 KB Output is correct
24 Correct 28 ms 40528 KB Output is correct
25 Correct 5 ms 16732 KB Output is correct
26 Correct 5 ms 16732 KB Output is correct
27 Correct 22 ms 31620 KB Output is correct
28 Correct 24 ms 34652 KB Output is correct
29 Correct 23 ms 34652 KB Output is correct
30 Correct 23 ms 34424 KB Output is correct
31 Correct 27 ms 31064 KB Output is correct
32 Correct 22 ms 31060 KB Output is correct
33 Correct 29 ms 41296 KB Output is correct
34 Correct 38 ms 47964 KB Output is correct
35 Correct 29 ms 39516 KB Output is correct
36 Correct 35 ms 47192 KB Output is correct
37 Correct 5 ms 16984 KB Output is correct
38 Correct 6 ms 17244 KB Output is correct
39 Correct 118 ms 22868 KB Output is correct
40 Correct 109 ms 24656 KB Output is correct
41 Correct 120 ms 25684 KB Output is correct
42 Correct 122 ms 25680 KB Output is correct
43 Correct 171 ms 28756 KB Output is correct
44 Correct 130 ms 28540 KB Output is correct
45 Correct 85 ms 17360 KB Output is correct
46 Correct 83 ms 17760 KB Output is correct
47 Correct 103 ms 23380 KB Output is correct
48 Correct 108 ms 23380 KB Output is correct
49 Correct 118 ms 23232 KB Output is correct
50 Correct 114 ms 23224 KB Output is correct
51 Correct 98 ms 24916 KB Output is correct
52 Correct 112 ms 25916 KB Output is correct
53 Correct 138 ms 28248 KB Output is correct
54 Correct 126 ms 28464 KB Output is correct
55 Runtime error 606 ms 524288 KB Execution killed with signal 9
56 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22616 KB Output is correct
2 Correct 17 ms 28252 KB Output is correct
3 Correct 19 ms 30092 KB Output is correct
4 Correct 29 ms 40792 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 5 ms 16864 KB Output is correct
7 Correct 24 ms 34140 KB Output is correct
8 Correct 22 ms 33860 KB Output is correct
9 Correct 23 ms 33884 KB Output is correct
10 Correct 23 ms 34908 KB Output is correct
11 Correct 23 ms 35392 KB Output is correct
12 Correct 23 ms 34248 KB Output is correct
13 Correct 30 ms 42588 KB Output is correct
14 Correct 37 ms 47700 KB Output is correct
15 Correct 23 ms 32348 KB Output is correct
16 Correct 36 ms 47440 KB Output is correct
17 Correct 14 ms 25948 KB Output is correct
18 Correct 20 ms 30772 KB Output is correct
19 Correct 6 ms 17244 KB Output is correct
20 Correct 6 ms 17248 KB Output is correct
21 Correct 16 ms 27228 KB Output is correct
22 Correct 17 ms 28416 KB Output is correct
23 Correct 21 ms 32604 KB Output is correct
24 Correct 28 ms 40528 KB Output is correct
25 Correct 5 ms 16732 KB Output is correct
26 Correct 5 ms 16732 KB Output is correct
27 Correct 22 ms 31620 KB Output is correct
28 Correct 24 ms 34652 KB Output is correct
29 Correct 23 ms 34652 KB Output is correct
30 Correct 23 ms 34424 KB Output is correct
31 Correct 27 ms 31064 KB Output is correct
32 Correct 22 ms 31060 KB Output is correct
33 Correct 29 ms 41296 KB Output is correct
34 Correct 38 ms 47964 KB Output is correct
35 Correct 29 ms 39516 KB Output is correct
36 Correct 35 ms 47192 KB Output is correct
37 Correct 5 ms 16984 KB Output is correct
38 Correct 6 ms 17244 KB Output is correct
39 Correct 118 ms 22868 KB Output is correct
40 Correct 109 ms 24656 KB Output is correct
41 Correct 120 ms 25684 KB Output is correct
42 Correct 122 ms 25680 KB Output is correct
43 Correct 171 ms 28756 KB Output is correct
44 Correct 130 ms 28540 KB Output is correct
45 Correct 85 ms 17360 KB Output is correct
46 Correct 83 ms 17760 KB Output is correct
47 Correct 103 ms 23380 KB Output is correct
48 Correct 108 ms 23380 KB Output is correct
49 Correct 118 ms 23232 KB Output is correct
50 Correct 114 ms 23224 KB Output is correct
51 Correct 98 ms 24916 KB Output is correct
52 Correct 112 ms 25916 KB Output is correct
53 Correct 138 ms 28248 KB Output is correct
54 Correct 126 ms 28464 KB Output is correct
55 Runtime error 747 ms 524288 KB Execution killed with signal 9
56 Halted 0 ms 0 KB -