oj.uz

Submission #794915

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

struct fenw {
        long long bit[N];
        void add(int r, int d) {
                r++;
                for (; r < N; r += r & -r)
                        bit[r] += d;
        }
        long long get(int r) {
                r++;
                long long re = 0;
                for (; r; r &= (r - 1)) 
                        re += bit[r];
                return re;
        }
        int find(long long 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) {
                if (t[query_ind] == 1)
                        ad[v].push_back({query_ind, K[query_ind]});
                else
                        del[v].push_back({query_ind, K[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];
}
ll 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, K]: ad[v]) {
                pos.add(i, K);
                all.add(i, K);
                add(1, 0, q, i, q, K);
        }
        for (auto [i, K]: del[v]) {
                all.add(i, -K);
                add(1, 0, q, i, q, -K);
        }
        if (l + 1 == r) {
                for (auto P: GET[l]) {
                        ll b = P[0];
                        int i = P[1];
                        ll all_pos = pos.get(i), mn = get(1, 0, q, 0, i + 1), sz = all.get(i) - (mn < 0 ? mn : 0);
                        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, K]: ad[v]) {
                pos.add(i, -K);
                all.add(i, -K);
                add(1, 0, q, i, q, -K);
        }
        for (auto [i, K]: del[v]) {
                all.add(i, K);
                add(1, 0, q, i, q, K);
        }
}

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({B[i], 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(long long int, long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'void add(long long int, long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:60:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'll get(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:74:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'void solve(long long int, long long int, long long int)':
foodcourt.cpp:98:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |                 int m = l + r >> 1;
      |                         ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 64212 KB Output is correct
2 Correct 33 ms 64276 KB Output is correct
3 Correct 33 ms 64272 KB Output is correct
4 Correct 34 ms 64432 KB Output is correct
5 Correct 31 ms 64144 KB Output is correct
6 Correct 29 ms 64084 KB Output is correct
7 Correct 35 ms 64340 KB Output is correct
8 Correct 34 ms 64424 KB Output is correct
9 Correct 35 ms 64400 KB Output is correct
10 Correct 39 ms 64372 KB Output is correct
11 Correct 35 ms 64460 KB Output is correct
12 Correct 36 ms 64480 KB Output is correct
13 Correct 29 ms 64096 KB Output is correct
14 Correct 30 ms 64160 KB Output is correct
15 Correct 33 ms 64340 KB Output is correct
16 Correct 35 ms 64596 KB Output is correct
17 Correct 33 ms 64348 KB Output is correct
18 Correct 34 ms 64452 KB Output is correct
19 Correct 31 ms 64084 KB Output is correct
20 Correct 32 ms 64212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 64212 KB Output is correct
2 Correct 33 ms 64276 KB Output is correct
3 Correct 33 ms 64272 KB Output is correct
4 Correct 34 ms 64432 KB Output is correct
5 Correct 31 ms 64144 KB Output is correct
6 Correct 29 ms 64084 KB Output is correct
7 Correct 35 ms 64340 KB Output is correct
8 Correct 34 ms 64424 KB Output is correct
9 Correct 35 ms 64400 KB Output is correct
10 Correct 39 ms 64372 KB Output is correct
11 Correct 35 ms 64460 KB Output is correct
12 Correct 36 ms 64480 KB Output is correct
13 Correct 29 ms 64096 KB Output is correct
14 Correct 30 ms 64160 KB Output is correct
15 Correct 33 ms 64340 KB Output is correct
16 Correct 35 ms 64596 KB Output is correct
17 Correct 33 ms 64348 KB Output is correct
18 Correct 34 ms 64452 KB Output is correct
19 Correct 31 ms 64084 KB Output is correct
20 Correct 32 ms 64212 KB Output is correct
21 Correct 34 ms 64352 KB Output is correct
22 Correct 33 ms 64328 KB Output is correct
23 Correct 42 ms 64388 KB Output is correct
24 Correct 34 ms 64424 KB Output is correct
25 Correct 30 ms 64084 KB Output is correct
26 Correct 33 ms 64020 KB Output is correct
27 Correct 34 ms 64424 KB Output is correct
28 Correct 35 ms 64468 KB Output is correct
29 Correct 34 ms 64400 KB Output is correct
30 Correct 35 ms 64400 KB Output is correct
31 Correct 35 ms 64328 KB Output is correct
32 Correct 35 ms 64444 KB Output is correct
33 Correct 30 ms 64084 KB Output is correct
34 Correct 31 ms 64144 KB Output is correct
35 Correct 36 ms 64544 KB Output is correct
36 Correct 36 ms 64576 KB Output is correct
37 Correct 31 ms 64072 KB Output is correct
38 Correct 32 ms 64080 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 79780 KB Output is correct
2 Correct 207 ms 78576 KB Output is correct
3 Correct 216 ms 80200 KB Output is correct
4 Correct 222 ms 80228 KB Output is correct
5 Correct 221 ms 79348 KB Output is correct
6 Correct 224 ms 79232 KB Output is correct
7 Correct 60 ms 71388 KB Output is correct
8 Correct 61 ms 71572 KB Output is correct
9 Correct 248 ms 80532 KB Output is correct
10 Correct 235 ms 80956 KB Output is correct
11 Correct 224 ms 80800 KB Output is correct
12 Correct 241 ms 80912 KB Output is correct
13 Correct 144 ms 75692 KB Output is correct
14 Correct 203 ms 76832 KB Output is correct
15 Correct 143 ms 74900 KB Output is correct
16 Correct 163 ms 75008 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 64212 KB Output is correct
2 Correct 33 ms 64276 KB Output is correct
3 Correct 33 ms 64272 KB Output is correct
4 Correct 34 ms 64432 KB Output is correct
5 Correct 31 ms 64144 KB Output is correct
6 Correct 29 ms 64084 KB Output is correct
7 Correct 35 ms 64340 KB Output is correct
8 Correct 34 ms 64424 KB Output is correct
9 Correct 35 ms 64400 KB Output is correct
10 Correct 39 ms 64372 KB Output is correct
11 Correct 35 ms 64460 KB Output is correct
12 Correct 36 ms 64480 KB Output is correct
13 Correct 29 ms 64096 KB Output is correct
14 Correct 30 ms 64160 KB Output is correct
15 Correct 33 ms 64340 KB Output is correct
16 Correct 35 ms 64596 KB Output is correct
17 Correct 33 ms 64348 KB Output is correct
18 Correct 34 ms 64452 KB Output is correct
19 Correct 31 ms 64084 KB Output is correct
20 Correct 32 ms 64212 KB Output is correct
21 Correct 253 ms 79780 KB Output is correct
22 Correct 207 ms 78576 KB Output is correct
23 Correct 216 ms 80200 KB Output is correct
24 Correct 222 ms 80228 KB Output is correct
25 Correct 221 ms 79348 KB Output is correct
26 Correct 224 ms 79232 KB Output is correct
27 Correct 60 ms 71388 KB Output is correct
28 Correct 61 ms 71572 KB Output is correct
29 Correct 248 ms 80532 KB Output is correct
30 Correct 235 ms 80956 KB Output is correct
31 Correct 224 ms 80800 KB Output is correct
32 Correct 241 ms 80912 KB Output is correct
33 Correct 144 ms 75692 KB Output is correct
34 Correct 203 ms 76832 KB Output is correct
35 Correct 143 ms 74900 KB Output is correct
36 Correct 163 ms 75008 KB Output is correct
37 Correct 293 ms 83080 KB Output is correct
38 Correct 296 ms 82620 KB Output is correct
39 Correct 57 ms 70672 KB Output is correct
40 Correct 63 ms 71524 KB Output is correct
41 Correct 335 ms 86736 KB Output is correct
42 Correct 381 ms 87280 KB Output is correct
43 Correct 359 ms 87180 KB Output is correct
44 Correct 389 ms 86928 KB Output is correct
45 Correct 355 ms 87156 KB Output is correct
46 Correct 359 ms 87080 KB Output is correct
47 Correct 72 ms 71940 KB Output is correct
48 Correct 372 ms 88680 KB Output is correct
49 Correct 254 ms 81064 KB Output is correct
50 Correct 316 ms 84476 KB Output is correct
51 Correct 388 ms 87624 KB Output is correct
52 Correct 375 ms 87668 KB Output is correct
53 Correct 120 ms 73128 KB Output is correct
54 Correct 141 ms 74980 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 80140 KB Output is correct
2 Correct 309 ms 81080 KB Output is correct
3 Correct 251 ms 81608 KB Output is correct
4 Correct 197 ms 77424 KB Output is correct
5 Correct 237 ms 80008 KB Output is correct
6 Correct 272 ms 82224 KB Output is correct
7 Correct 63 ms 71352 KB Output is correct
8 Correct 63 ms 70860 KB Output is correct
9 Correct 83 ms 72156 KB Output is correct
10 Correct 221 ms 78004 KB Output is correct
11 Correct 340 ms 83480 KB Output is correct
12 Correct 291 ms 83444 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 64212 KB Output is correct
2 Correct 33 ms 64276 KB Output is correct
3 Correct 33 ms 64272 KB Output is correct
4 Correct 34 ms 64432 KB Output is correct
5 Correct 31 ms 64144 KB Output is correct
6 Correct 29 ms 64084 KB Output is correct
7 Correct 35 ms 64340 KB Output is correct
8 Correct 34 ms 64424 KB Output is correct
9 Correct 35 ms 64400 KB Output is correct
10 Correct 39 ms 64372 KB Output is correct
11 Correct 35 ms 64460 KB Output is correct
12 Correct 36 ms 64480 KB Output is correct
13 Correct 29 ms 64096 KB Output is correct
14 Correct 30 ms 64160 KB Output is correct
15 Correct 33 ms 64340 KB Output is correct
16 Correct 35 ms 64596 KB Output is correct
17 Correct 33 ms 64348 KB Output is correct
18 Correct 34 ms 64452 KB Output is correct
19 Correct 31 ms 64084 KB Output is correct
20 Correct 32 ms 64212 KB Output is correct
21 Correct 34 ms 64352 KB Output is correct
22 Correct 33 ms 64328 KB Output is correct
23 Correct 42 ms 64388 KB Output is correct
24 Correct 34 ms 64424 KB Output is correct
25 Correct 30 ms 64084 KB Output is correct
26 Correct 33 ms 64020 KB Output is correct
27 Correct 34 ms 64424 KB Output is correct
28 Correct 35 ms 64468 KB Output is correct
29 Correct 34 ms 64400 KB Output is correct
30 Correct 35 ms 64400 KB Output is correct
31 Correct 35 ms 64328 KB Output is correct
32 Correct 35 ms 64444 KB Output is correct
33 Correct 30 ms 64084 KB Output is correct
34 Correct 31 ms 64144 KB Output is correct
35 Correct 36 ms 64544 KB Output is correct
36 Correct 36 ms 64576 KB Output is correct
37 Correct 31 ms 64072 KB Output is correct
38 Correct 32 ms 64080 KB Output is correct
39 Correct 253 ms 79780 KB Output is correct
40 Correct 207 ms 78576 KB Output is correct
41 Correct 216 ms 80200 KB Output is correct
42 Correct 222 ms 80228 KB Output is correct
43 Correct 221 ms 79348 KB Output is correct
44 Correct 224 ms 79232 KB Output is correct
45 Correct 60 ms 71388 KB Output is correct
46 Correct 61 ms 71572 KB Output is correct
47 Correct 248 ms 80532 KB Output is correct
48 Correct 235 ms 80956 KB Output is correct
49 Correct 224 ms 80800 KB Output is correct
50 Correct 241 ms 80912 KB Output is correct
51 Correct 144 ms 75692 KB Output is correct
52 Correct 203 ms 76832 KB Output is correct
53 Correct 143 ms 74900 KB Output is correct
54 Correct 163 ms 75008 KB Output is correct
55 Correct 293 ms 83080 KB Output is correct
56 Correct 296 ms 82620 KB Output is correct
57 Correct 57 ms 70672 KB Output is correct
58 Correct 63 ms 71524 KB Output is correct
59 Correct 335 ms 86736 KB Output is correct
60 Correct 381 ms 87280 KB Output is correct
61 Correct 359 ms 87180 KB Output is correct
62 Correct 389 ms 86928 KB Output is correct
63 Correct 355 ms 87156 KB Output is correct
64 Correct 359 ms 87080 KB Output is correct
65 Correct 72 ms 71940 KB Output is correct
66 Correct 372 ms 88680 KB Output is correct
67 Correct 254 ms 81064 KB Output is correct
68 Correct 316 ms 84476 KB Output is correct
69 Correct 388 ms 87624 KB Output is correct
70 Correct 375 ms 87668 KB Output is correct
71 Correct 120 ms 73128 KB Output is correct
72 Correct 141 ms 74980 KB Output is correct
73 Correct 234 ms 80140 KB Output is correct
74 Correct 309 ms 81080 KB Output is correct
75 Correct 251 ms 81608 KB Output is correct
76 Correct 197 ms 77424 KB Output is correct
77 Correct 237 ms 80008 KB Output is correct
78 Correct 272 ms 82224 KB Output is correct
79 Correct 63 ms 71352 KB Output is correct
80 Correct 63 ms 70860 KB Output is correct
81 Correct 83 ms 72156 KB Output is correct
82 Correct 221 ms 78004 KB Output is correct
83 Correct 340 ms 83480 KB Output is correct
84 Correct 291 ms 83444 KB Output is correct
85 Correct 297 ms 83084 KB Output is correct
86 Correct 352 ms 85180 KB Output is correct
87 Correct 327 ms 84288 KB Output is correct
88 Correct 373 ms 86752 KB Output is correct
89 Correct 246 ms 79756 KB Output is correct
90 Correct 374 ms 87232 KB Output is correct
91 Correct 295 ms 83168 KB Output is correct
92 Correct 301 ms 82056 KB Output is correct
93 Correct 373 ms 87144 KB Output is correct
94 Correct 394 ms 86964 KB Output is correct
95 Correct 366 ms 86564 KB Output is correct
96 Correct 406 ms 87184 KB Output is correct
97 Correct 376 ms 87220 KB Output is correct
98 Correct 291 ms 83832 KB Output is correct
99 Correct 74 ms 71980 KB Output is correct
100 Correct 301 ms 84188 KB Output is correct
101 Correct 343 ms 88796 KB Output is correct
102 Correct 209 ms 79020 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 64212 KB Output is correct
2 Correct 33 ms 64276 KB Output is correct
3 Correct 33 ms 64272 KB Output is correct
4 Correct 34 ms 64432 KB Output is correct
5 Correct 31 ms 64144 KB Output is correct
6 Correct 29 ms 64084 KB Output is correct
7 Correct 35 ms 64340 KB Output is correct
8 Correct 34 ms 64424 KB Output is correct
9 Correct 35 ms 64400 KB Output is correct
10 Correct 39 ms 64372 KB Output is correct
11 Correct 35 ms 64460 KB Output is correct
12 Correct 36 ms 64480 KB Output is correct
13 Correct 29 ms 64096 KB Output is correct
14 Correct 30 ms 64160 KB Output is correct
15 Correct 33 ms 64340 KB Output is correct
16 Correct 35 ms 64596 KB Output is correct
17 Correct 33 ms 64348 KB Output is correct
18 Correct 34 ms 64452 KB Output is correct
19 Correct 31 ms 64084 KB Output is correct
20 Correct 32 ms 64212 KB Output is correct
21 Correct 34 ms 64352 KB Output is correct
22 Correct 33 ms 64328 KB Output is correct
23 Correct 42 ms 64388 KB Output is correct
24 Correct 34 ms 64424 KB Output is correct
25 Correct 30 ms 64084 KB Output is correct
26 Correct 33 ms 64020 KB Output is correct
27 Correct 34 ms 64424 KB Output is correct
28 Correct 35 ms 64468 KB Output is correct
29 Correct 34 ms 64400 KB Output is correct
30 Correct 35 ms 64400 KB Output is correct
31 Correct 35 ms 64328 KB Output is correct
32 Correct 35 ms 64444 KB Output is correct
33 Correct 30 ms 64084 KB Output is correct
34 Correct 31 ms 64144 KB Output is correct
35 Correct 36 ms 64544 KB Output is correct
36 Correct 36 ms 64576 KB Output is correct
37 Correct 31 ms 64072 KB Output is correct
38 Correct 32 ms 64080 KB Output is correct
39 Correct 253 ms 79780 KB Output is correct
40 Correct 207 ms 78576 KB Output is correct
41 Correct 216 ms 80200 KB Output is correct
42 Correct 222 ms 80228 KB Output is correct
43 Correct 221 ms 79348 KB Output is correct
44 Correct 224 ms 79232 KB Output is correct
45 Correct 60 ms 71388 KB Output is correct
46 Correct 61 ms 71572 KB Output is correct
47 Correct 248 ms 80532 KB Output is correct
48 Correct 235 ms 80956 KB Output is correct
49 Correct 224 ms 80800 KB Output is correct
50 Correct 241 ms 80912 KB Output is correct
51 Correct 144 ms 75692 KB Output is correct
52 Correct 203 ms 76832 KB Output is correct
53 Correct 143 ms 74900 KB Output is correct
54 Correct 163 ms 75008 KB Output is correct
55 Execution timed out 1084 ms 144332 KB Time limit exceeded
56 Halted 0 ms 0 KB -