oj.uz

Submission #794912

# Submission time Handle Problem Language Result Execution time Memory
794912 2023-07-27T03:42:30 Z RushB Food Court (JOI21_foodcourt) C++17
68 / 100
 1000 ms 91860 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 
#define int int64_t
const int64_t INF = 1ll << 60;
const int N = 3e5;
const int LG = 20;
int A[N], B[N], L[N], R[N], K[N], C[N], n, m, q, mn[N << 2], delta[N << 2], ans[N];
vector<int> V[4 * N], GET[N];
short t[N];

struct fenw {
        int bit[N];
        void add(int r, int d) {
                r++;
                for (; r < N; r += r & -r)
                        bit[r] += d;
        }
        int get(int r) {
                r++;
                int re = 0;
                for (; r; r &= (r - 1)) 
                        re += bit[r];
                return re;
        }
        int find(int x) {
                int pos = 0;
                for (int i = LG; i >= 0; i--) {
                        if (pos + (1 << i) < N && bit[pos + (1 << i)] < x) {
                                pos += 1 << i;
                                x -= bit[pos];
                        }
                }
                return pos;
        }
} pos, all;

void add_query(int v, int l, int r, int L, int R, int query_ind) {
        if (R <= l || r <= L) return;
        if (L <= l && r <= R) {
                V[v].push_back(query_ind);
                return;
        }
        int m = l + r >> 1;
        add_query(v << 1, l, m, L, R, query_ind);
        add_query(v << 1 | 1, m, r, L, R, query_ind);
}

void add(int v, int l, int r, int L, int R, int d) {
        if (L <= l && r <= R) {
                mn[v] += d;
                delta[v] += d;
                return;
        }
        int m = l + r >> 1;
        if (R <= m)
                add(v << 1, l, m, L, R, d);
        else if (L >= m)
                add(v << 1 | 1, m, r, L, R, d);
        else {
                add(v << 1, l, m, L, R, d);
                add(v << 1 | 1, m, r, L, R, d);
        }
        mn[v] = min(mn[v << 1], mn[v << 1 | 1]) + delta[v];
}
int get(int v, int l, int r, int L, int R) {
        if (R <= l || r <= L) return INF;
        if (L <= l && r <= R) return mn[v];
        int m = l + r >> 1;
        return min(get(v << 1, l, m, L, R), get(v << 1 | 1, m, r, L, R)) + delta[v];
}

void solve(int v, int l, int r) {
        for (auto i: V[v]) {
                if (t[i] == 1) {
                        pos.add(i, K[i]);
                        all.add(i, K[i]);
                        add(1, 0, q, i, q, K[i]);
                }
                else {
                        all.add(i, -K[i]);
                        add(1, 0, q, i, q, -K[i]);
                }
        }
        if (l + 1 == r) {
                for (auto i: GET[l]) {
                        int all_pos = pos.get(i), mn = get(1, 0, q, 0, i + 1), sz = all.get(i) - (mn < 0 ? mn : 0), b = B[i];
                        b += all_pos - sz;
                        ans[i] = (b <= all_pos ? pos.find(b) : N);
                }
        }
        else {
                int m = l + r >> 1;
                solve(v << 1, l, m);
                solve(v << 1 | 1, m, r);
        }
        for (auto i: V[v]) {
                if (t[i] == 1) {
                        pos.add(i, -K[i]);
                        all.add(i, -K[i]);
                        add(1, 0, q, i, q, -K[i]);
                }
                else {
                        all.add(i, +K[i]);
                        add(1, 0, q, i, q, +K[i]);
                }
        }
}

signed main() {
        ios::sync_with_stdio(0), cin.tie(0);
        cin >> n >> m >> q;
        FOR(i, 0, q) {
                cin >> t[i];
                if (t[i] == 1) {
                        cin >> L[i] >> R[i] >> C[i] >> K[i];
                        L[i]--;
                        add_query(1, 0, n, L[i], R[i], i);
                        R[i]--;
                }
                else if (t[i] == 2) {
                        cin >> L[i] >> R[i] >> K[i];
                        L[i]--;
                        add_query(1, 0, n, L[i], R[i], i);
                        R[i]--;
                }
                else {
                        cin >> A[i] >> B[i];
                        A[i]--;
                        GET[A[i]].push_back(i);
                }
        }
        solve(1, 0, n);
        FOR(i, 0, q) if (t[i] == 3)
               cout << (ans[i] == N ? 0 : C[ans[i]]) << '\n'; 
}
//06:22:05

Compilation message

foodcourt.cpp: In function 'void add_query(int64_t, int64_t, int64_t, int64_t, int64_t, int64_t)':
foodcourt.cpp:44:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'void add(int64_t, int64_t, int64_t, int64_t, int64_t, int64_t)':
foodcourt.cpp:55:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'int64_t get(int64_t, int64_t, int64_t, int64_t, int64_t)':
foodcourt.cpp:69:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'void solve(int64_t, int64_t, int64_t)':
foodcourt.cpp:93:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |                 int m = l + r >> 1;
      |                         ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35924 KB Output is correct
2 Correct 24 ms 36072 KB Output is correct
3 Correct 20 ms 35924 KB Output is correct
4 Correct 22 ms 36028 KB Output is correct
5 Correct 18 ms 35916 KB Output is correct
6 Correct 20 ms 35840 KB Output is correct
7 Correct 26 ms 36052 KB Output is correct
8 Correct 22 ms 36080 KB Output is correct
9 Correct 22 ms 36128 KB Output is correct
10 Correct 22 ms 36056 KB Output is correct
11 Correct 26 ms 36220 KB Output is correct
12 Correct 23 ms 36080 KB Output is correct
13 Correct 18 ms 35908 KB Output is correct
14 Correct 19 ms 35932 KB Output is correct
15 Correct 21 ms 35960 KB Output is correct
16 Correct 23 ms 36096 KB Output is correct
17 Correct 21 ms 35948 KB Output is correct
18 Correct 22 ms 36040 KB Output is correct
19 Correct 19 ms 35972 KB Output is correct
20 Correct 23 ms 35904 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35924 KB Output is correct
2 Correct 24 ms 36072 KB Output is correct
3 Correct 20 ms 35924 KB Output is correct
4 Correct 22 ms 36028 KB Output is correct
5 Correct 18 ms 35916 KB Output is correct
6 Correct 20 ms 35840 KB Output is correct
7 Correct 26 ms 36052 KB Output is correct
8 Correct 22 ms 36080 KB Output is correct
9 Correct 22 ms 36128 KB Output is correct
10 Correct 22 ms 36056 KB Output is correct
11 Correct 26 ms 36220 KB Output is correct
12 Correct 23 ms 36080 KB Output is correct
13 Correct 18 ms 35908 KB Output is correct
14 Correct 19 ms 35932 KB Output is correct
15 Correct 21 ms 35960 KB Output is correct
16 Correct 23 ms 36096 KB Output is correct
17 Correct 21 ms 35948 KB Output is correct
18 Correct 22 ms 36040 KB Output is correct
19 Correct 19 ms 35972 KB Output is correct
20 Correct 23 ms 35904 KB Output is correct
21 Correct 21 ms 36008 KB Output is correct
22 Correct 21 ms 35984 KB Output is correct
23 Correct 22 ms 35976 KB Output is correct
24 Correct 23 ms 36108 KB Output is correct
25 Correct 22 ms 35868 KB Output is correct
26 Correct 19 ms 35924 KB Output is correct
27 Correct 23 ms 36056 KB Output is correct
28 Correct 23 ms 36140 KB Output is correct
29 Correct 22 ms 36052 KB Output is correct
30 Correct 22 ms 36052 KB Output is correct
31 Correct 24 ms 36088 KB Output is correct
32 Correct 23 ms 36052 KB Output is correct
33 Correct 19 ms 35924 KB Output is correct
34 Correct 19 ms 35924 KB Output is correct
35 Correct 23 ms 36052 KB Output is correct
36 Correct 24 ms 36064 KB Output is correct
37 Correct 20 ms 35824 KB Output is correct
38 Correct 20 ms 35924 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 48220 KB Output is correct
2 Correct 177 ms 47504 KB Output is correct
3 Correct 194 ms 48384 KB Output is correct
4 Correct 203 ms 48432 KB Output is correct
5 Correct 231 ms 47820 KB Output is correct
6 Correct 182 ms 47832 KB Output is correct
7 Correct 47 ms 42740 KB Output is correct
8 Correct 53 ms 42940 KB Output is correct
9 Correct 200 ms 48256 KB Output is correct
10 Correct 208 ms 48716 KB Output is correct
11 Correct 223 ms 48568 KB Output is correct
12 Correct 215 ms 48620 KB Output is correct
13 Correct 126 ms 45604 KB Output is correct
14 Correct 145 ms 46684 KB Output is correct
15 Correct 123 ms 45344 KB Output is correct
16 Correct 128 ms 45676 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 91860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35924 KB Output is correct
2 Correct 24 ms 36072 KB Output is correct
3 Correct 20 ms 35924 KB Output is correct
4 Correct 22 ms 36028 KB Output is correct
5 Correct 18 ms 35916 KB Output is correct
6 Correct 20 ms 35840 KB Output is correct
7 Correct 26 ms 36052 KB Output is correct
8 Correct 22 ms 36080 KB Output is correct
9 Correct 22 ms 36128 KB Output is correct
10 Correct 22 ms 36056 KB Output is correct
11 Correct 26 ms 36220 KB Output is correct
12 Correct 23 ms 36080 KB Output is correct
13 Correct 18 ms 35908 KB Output is correct
14 Correct 19 ms 35932 KB Output is correct
15 Correct 21 ms 35960 KB Output is correct
16 Correct 23 ms 36096 KB Output is correct
17 Correct 21 ms 35948 KB Output is correct
18 Correct 22 ms 36040 KB Output is correct
19 Correct 19 ms 35972 KB Output is correct
20 Correct 23 ms 35904 KB Output is correct
21 Correct 185 ms 48220 KB Output is correct
22 Correct 177 ms 47504 KB Output is correct
23 Correct 194 ms 48384 KB Output is correct
24 Correct 203 ms 48432 KB Output is correct
25 Correct 231 ms 47820 KB Output is correct
26 Correct 182 ms 47832 KB Output is correct
27 Correct 47 ms 42740 KB Output is correct
28 Correct 53 ms 42940 KB Output is correct
29 Correct 200 ms 48256 KB Output is correct
30 Correct 208 ms 48716 KB Output is correct
31 Correct 223 ms 48568 KB Output is correct
32 Correct 215 ms 48620 KB Output is correct
33 Correct 126 ms 45604 KB Output is correct
34 Correct 145 ms 46684 KB Output is correct
35 Correct 123 ms 45344 KB Output is correct
36 Correct 128 ms 45676 KB Output is correct
37 Correct 251 ms 49308 KB Output is correct
38 Correct 277 ms 48772 KB Output is correct
39 Correct 43 ms 42180 KB Output is correct
40 Correct 48 ms 42736 KB Output is correct
41 Correct 307 ms 51004 KB Output is correct
42 Correct 342 ms 51560 KB Output is correct
43 Correct 323 ms 51592 KB Output is correct
44 Correct 330 ms 51304 KB Output is correct
45 Correct 318 ms 51580 KB Output is correct
46 Correct 328 ms 51696 KB Output is correct
47 Correct 63 ms 43436 KB Output is correct
48 Correct 324 ms 51728 KB Output is correct
49 Correct 224 ms 47584 KB Output is correct
50 Correct 285 ms 49872 KB Output is correct
51 Correct 332 ms 51812 KB Output is correct
52 Correct 344 ms 51868 KB Output is correct
53 Correct 98 ms 43980 KB Output is correct
54 Correct 117 ms 45644 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 47972 KB Output is correct
2 Correct 227 ms 48844 KB Output is correct
3 Correct 242 ms 49216 KB Output is correct
4 Correct 206 ms 46128 KB Output is correct
5 Correct 215 ms 47888 KB Output is correct
6 Correct 256 ms 49464 KB Output is correct
7 Correct 49 ms 42544 KB Output is correct
8 Correct 48 ms 42308 KB Output is correct
9 Correct 61 ms 43588 KB Output is correct
10 Correct 185 ms 45644 KB Output is correct
11 Correct 270 ms 49308 KB Output is correct
12 Correct 268 ms 49420 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35924 KB Output is correct
2 Correct 24 ms 36072 KB Output is correct
3 Correct 20 ms 35924 KB Output is correct
4 Correct 22 ms 36028 KB Output is correct
5 Correct 18 ms 35916 KB Output is correct
6 Correct 20 ms 35840 KB Output is correct
7 Correct 26 ms 36052 KB Output is correct
8 Correct 22 ms 36080 KB Output is correct
9 Correct 22 ms 36128 KB Output is correct
10 Correct 22 ms 36056 KB Output is correct
11 Correct 26 ms 36220 KB Output is correct
12 Correct 23 ms 36080 KB Output is correct
13 Correct 18 ms 35908 KB Output is correct
14 Correct 19 ms 35932 KB Output is correct
15 Correct 21 ms 35960 KB Output is correct
16 Correct 23 ms 36096 KB Output is correct
17 Correct 21 ms 35948 KB Output is correct
18 Correct 22 ms 36040 KB Output is correct
19 Correct 19 ms 35972 KB Output is correct
20 Correct 23 ms 35904 KB Output is correct
21 Correct 21 ms 36008 KB Output is correct
22 Correct 21 ms 35984 KB Output is correct
23 Correct 22 ms 35976 KB Output is correct
24 Correct 23 ms 36108 KB Output is correct
25 Correct 22 ms 35868 KB Output is correct
26 Correct 19 ms 35924 KB Output is correct
27 Correct 23 ms 36056 KB Output is correct
28 Correct 23 ms 36140 KB Output is correct
29 Correct 22 ms 36052 KB Output is correct
30 Correct 22 ms 36052 KB Output is correct
31 Correct 24 ms 36088 KB Output is correct
32 Correct 23 ms 36052 KB Output is correct
33 Correct 19 ms 35924 KB Output is correct
34 Correct 19 ms 35924 KB Output is correct
35 Correct 23 ms 36052 KB Output is correct
36 Correct 24 ms 36064 KB Output is correct
37 Correct 20 ms 35824 KB Output is correct
38 Correct 20 ms 35924 KB Output is correct
39 Correct 185 ms 48220 KB Output is correct
40 Correct 177 ms 47504 KB Output is correct
41 Correct 194 ms 48384 KB Output is correct
42 Correct 203 ms 48432 KB Output is correct
43 Correct 231 ms 47820 KB Output is correct
44 Correct 182 ms 47832 KB Output is correct
45 Correct 47 ms 42740 KB Output is correct
46 Correct 53 ms 42940 KB Output is correct
47 Correct 200 ms 48256 KB Output is correct
48 Correct 208 ms 48716 KB Output is correct
49 Correct 223 ms 48568 KB Output is correct
50 Correct 215 ms 48620 KB Output is correct
51 Correct 126 ms 45604 KB Output is correct
52 Correct 145 ms 46684 KB Output is correct
53 Correct 123 ms 45344 KB Output is correct
54 Correct 128 ms 45676 KB Output is correct
55 Correct 251 ms 49308 KB Output is correct
56 Correct 277 ms 48772 KB Output is correct
57 Correct 43 ms 42180 KB Output is correct
58 Correct 48 ms 42736 KB Output is correct
59 Correct 307 ms 51004 KB Output is correct
60 Correct 342 ms 51560 KB Output is correct
61 Correct 323 ms 51592 KB Output is correct
62 Correct 330 ms 51304 KB Output is correct
63 Correct 318 ms 51580 KB Output is correct
64 Correct 328 ms 51696 KB Output is correct
65 Correct 63 ms 43436 KB Output is correct
66 Correct 324 ms 51728 KB Output is correct
67 Correct 224 ms 47584 KB Output is correct
68 Correct 285 ms 49872 KB Output is correct
69 Correct 332 ms 51812 KB Output is correct
70 Correct 344 ms 51868 KB Output is correct
71 Correct 98 ms 43980 KB Output is correct
72 Correct 117 ms 45644 KB Output is correct
73 Correct 233 ms 47972 KB Output is correct
74 Correct 227 ms 48844 KB Output is correct
75 Correct 242 ms 49216 KB Output is correct
76 Correct 206 ms 46128 KB Output is correct
77 Correct 215 ms 47888 KB Output is correct
78 Correct 256 ms 49464 KB Output is correct
79 Correct 49 ms 42544 KB Output is correct
80 Correct 48 ms 42308 KB Output is correct
81 Correct 61 ms 43588 KB Output is correct
82 Correct 185 ms 45644 KB Output is correct
83 Correct 270 ms 49308 KB Output is correct
84 Correct 268 ms 49420 KB Output is correct
85 Correct 256 ms 49368 KB Output is correct
86 Correct 321 ms 50712 KB Output is correct
87 Correct 300 ms 49804 KB Output is correct
88 Correct 327 ms 51544 KB Output is correct
89 Correct 210 ms 46796 KB Output is correct
90 Correct 323 ms 51516 KB Output is correct
91 Correct 262 ms 48900 KB Output is correct
92 Correct 240 ms 48324 KB Output is correct
93 Correct 324 ms 51580 KB Output is correct
94 Correct 322 ms 51324 KB Output is correct
95 Correct 332 ms 51164 KB Output is correct
96 Correct 334 ms 51696 KB Output is correct
97 Correct 362 ms 51656 KB Output is correct
98 Correct 305 ms 49332 KB Output is correct
99 Correct 60 ms 43340 KB Output is correct
100 Correct 271 ms 48816 KB Output is correct
101 Correct 329 ms 51772 KB Output is correct
102 Correct 233 ms 47308 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35924 KB Output is correct
2 Correct 24 ms 36072 KB Output is correct
3 Correct 20 ms 35924 KB Output is correct
4 Correct 22 ms 36028 KB Output is correct
5 Correct 18 ms 35916 KB Output is correct
6 Correct 20 ms 35840 KB Output is correct
7 Correct 26 ms 36052 KB Output is correct
8 Correct 22 ms 36080 KB Output is correct
9 Correct 22 ms 36128 KB Output is correct
10 Correct 22 ms 36056 KB Output is correct
11 Correct 26 ms 36220 KB Output is correct
12 Correct 23 ms 36080 KB Output is correct
13 Correct 18 ms 35908 KB Output is correct
14 Correct 19 ms 35932 KB Output is correct
15 Correct 21 ms 35960 KB Output is correct
16 Correct 23 ms 36096 KB Output is correct
17 Correct 21 ms 35948 KB Output is correct
18 Correct 22 ms 36040 KB Output is correct
19 Correct 19 ms 35972 KB Output is correct
20 Correct 23 ms 35904 KB Output is correct
21 Correct 21 ms 36008 KB Output is correct
22 Correct 21 ms 35984 KB Output is correct
23 Correct 22 ms 35976 KB Output is correct
24 Correct 23 ms 36108 KB Output is correct
25 Correct 22 ms 35868 KB Output is correct
26 Correct 19 ms 35924 KB Output is correct
27 Correct 23 ms 36056 KB Output is correct
28 Correct 23 ms 36140 KB Output is correct
29 Correct 22 ms 36052 KB Output is correct
30 Correct 22 ms 36052 KB Output is correct
31 Correct 24 ms 36088 KB Output is correct
32 Correct 23 ms 36052 KB Output is correct
33 Correct 19 ms 35924 KB Output is correct
34 Correct 19 ms 35924 KB Output is correct
35 Correct 23 ms 36052 KB Output is correct
36 Correct 24 ms 36064 KB Output is correct
37 Correct 20 ms 35824 KB Output is correct
38 Correct 20 ms 35924 KB Output is correct
39 Correct 185 ms 48220 KB Output is correct
40 Correct 177 ms 47504 KB Output is correct
41 Correct 194 ms 48384 KB Output is correct
42 Correct 203 ms 48432 KB Output is correct
43 Correct 231 ms 47820 KB Output is correct
44 Correct 182 ms 47832 KB Output is correct
45 Correct 47 ms 42740 KB Output is correct
46 Correct 53 ms 42940 KB Output is correct
47 Correct 200 ms 48256 KB Output is correct
48 Correct 208 ms 48716 KB Output is correct
49 Correct 223 ms 48568 KB Output is correct
50 Correct 215 ms 48620 KB Output is correct
51 Correct 126 ms 45604 KB Output is correct
52 Correct 145 ms 46684 KB Output is correct
53 Correct 123 ms 45344 KB Output is correct
54 Correct 128 ms 45676 KB Output is correct
55 Execution timed out 1061 ms 91860 KB Time limit exceeded
56 Halted 0 ms 0 KB -