# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
466517 |
2021-08-19T14:32:42 Z |
jhwest2 |
Cake 3 (JOI19_cake3) |
C++14 |
|
4000 ms |
122028 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pint;
const int M = 2e5 + 10;
const lint INF = 4e18 + 10;
lint n, m, ans, A[M], B[M], D[M];
pair<lint, lint> X[M];
struct Pst {
struct Node {
lint cnt, val, l, r;
Node() = default;
} T[30 * M];
int size = 0, rt = 0, R[M];
int new_node() { return ++size; }
void init(int lo = 1, int hi = n, int idx = 0) {
if (lo == hi) return;
init(lo, lo + hi >> 1, T[idx].l = new_node());
init(1 + (lo + hi >> 1), hi, T[idx].r = new_node());
}
void update(int a, lint x) {
R[++rt] = new_node();
_update(a, x, 1, n, R[rt - 1], R[rt]);
}
void _update(int a, lint x, int lo, int hi, int idx, int jdx) {
if (lo == hi) {
T[jdx].val = T[idx].val + x;
T[jdx].cnt = T[idx].cnt + 1;
return;
}
int m = lo + hi >> 1;
if (a <= m) {
_update(a, x, lo, m, T[idx].l, T[jdx].l = new_node());
T[jdx].r = T[idx].r;
}
else {
_update(a, x, m + 1, hi, T[idx].r, T[jdx].r = new_node());
T[jdx].l = T[idx].l;
}
T[jdx].val = T[T[jdx].l].val + T[T[jdx].r].val;
T[jdx].cnt = T[T[jdx].l].cnt + T[T[jdx].r].cnt;
}
lint query(int a, int b) {
int lo = 1, hi = rt;
while (lo < hi) {
int mid = lo + hi + 1 >> 1;
if (cnt_query(a, b, 1, n, R[mid]) > m) hi = mid - 1;
else lo = mid;
}
return sum_query(a, b, 1, n, R[lo]);
}
lint cnt_query(int a, int b, int lo, int hi, int idx) {
if (b < lo || a > hi) return 0;
if (a <= lo && hi <= b) return T[idx].cnt;
return cnt_query(a, b, lo, lo + hi >> 1, T[idx].l) +
cnt_query(a, b, 1 + (lo + hi >> 1), hi, T[idx].r);
}
lint sum_query(int a, int b, int lo, int hi, int idx) {
if (b < lo || a > hi) return 0;
if (a <= lo && hi <= b) return T[idx].val;
return sum_query(a, b, lo, lo + hi >> 1, T[idx].l) +
sum_query(a, b, 1 + (lo + hi >> 1), hi, T[idx].r);
}
} S;
void solve(lint l, lint r, lint lo, lint hi) {
if (l > r) return;
if (lo == hi) {
for (int i = l; i <= r; i++) {
D[i] = lo;
}
return;
}
lint mid = l + r >> 1, mx = -INF;
for (int i = max(lo, mid + m - 1); i <= hi; i++) {
lint x = S.query(mid, i) - 2 * (B[i] - B[mid]);
if (x > mx) mx = x, D[mid] = i;
}
solve(l, mid - 1, lo, D[mid]);
solve(mid + 1, r, D[mid], hi);
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> X[i].va >> X[i].vb;
}
sort(X + 1, X + n + 1, [&](auto a, auto b) {
return tie(a.vb, a.va) < tie(b.vb, b.va);
});
for (int i = 1; i <= n; i++) {
tie(A[i], B[i]) = X[i];
}
vector<pint> V;
for (int i = 1; i <= n; i++) {
V.emplace_back(A[i], i);
}
sort(V.rbegin(), V.rend());
for (auto [a, b] : V) S.update(b, a);
solve(1, n - m + 1, m, n);
lint ans = -INF;
for (int i = 1; i <= n; i++) {
if (D[i] - i + 1 < m) continue;
ans = max(ans, S.query(i, D[i]) - 2 * (B[D[i]] - B[i]));
}
cout << ans;
}
Compilation message
cake3.cpp: In member function 'void Pst::init(int, int, int)':
cake3.cpp:27:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | init(lo, lo + hi >> 1, T[idx].l = new_node());
| ~~~^~~~
cake3.cpp:28:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | init(1 + (lo + hi >> 1), hi, T[idx].r = new_node());
| ~~~^~~~
cake3.cpp: In member function 'void Pst::_update(int, lint, int, int, int, int)':
cake3.cpp:40:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int m = lo + hi >> 1;
| ~~~^~~~
cake3.cpp: In member function 'lint Pst::query(int, int)':
cake3.cpp:55:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int mid = lo + hi + 1 >> 1;
| ~~~~~~~~^~~
cake3.cpp: In member function 'lint Pst::cnt_query(int, int, int, int, int)':
cake3.cpp:64:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | return cnt_query(a, b, lo, lo + hi >> 1, T[idx].l) +
| ~~~^~~~
cake3.cpp:65:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | cnt_query(a, b, 1 + (lo + hi >> 1), hi, T[idx].r);
| ~~~^~~~
cake3.cpp: In member function 'lint Pst::sum_query(int, int, int, int, int)':
cake3.cpp:70:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | return sum_query(a, b, lo, lo + hi >> 1, T[idx].l) +
| ~~~^~~~
cake3.cpp:71:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | sum_query(a, b, 1 + (lo + hi >> 1), hi, T[idx].r);
| ~~~^~~~
cake3.cpp: In function 'void solve(lint, lint, lint, lint)':
cake3.cpp:82:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | lint mid = l + r >> 1, mx = -INF;
| ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:107:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
107 | for (auto [a, b] : V) S.update(b, a);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
452 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
328 KB |
Output is correct |
29 |
Correct |
1 ms |
328 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
452 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
328 KB |
Output is correct |
29 |
Correct |
1 ms |
328 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
336 KB |
Output is correct |
38 |
Correct |
22 ms |
1216 KB |
Output is correct |
39 |
Correct |
24 ms |
1228 KB |
Output is correct |
40 |
Correct |
12 ms |
1244 KB |
Output is correct |
41 |
Correct |
14 ms |
1220 KB |
Output is correct |
42 |
Correct |
7 ms |
1244 KB |
Output is correct |
43 |
Correct |
12 ms |
1192 KB |
Output is correct |
44 |
Correct |
21 ms |
1200 KB |
Output is correct |
45 |
Correct |
23 ms |
1256 KB |
Output is correct |
46 |
Correct |
23 ms |
1272 KB |
Output is correct |
47 |
Correct |
24 ms |
1244 KB |
Output is correct |
48 |
Correct |
22 ms |
1208 KB |
Output is correct |
49 |
Correct |
17 ms |
1356 KB |
Output is correct |
50 |
Correct |
18 ms |
1260 KB |
Output is correct |
51 |
Correct |
16 ms |
1252 KB |
Output is correct |
52 |
Correct |
14 ms |
1220 KB |
Output is correct |
53 |
Correct |
15 ms |
1244 KB |
Output is correct |
54 |
Correct |
10 ms |
1228 KB |
Output is correct |
55 |
Correct |
7 ms |
1236 KB |
Output is correct |
56 |
Correct |
7 ms |
1228 KB |
Output is correct |
57 |
Correct |
9 ms |
1100 KB |
Output is correct |
58 |
Correct |
8 ms |
1228 KB |
Output is correct |
59 |
Correct |
14 ms |
1208 KB |
Output is correct |
60 |
Correct |
22 ms |
1236 KB |
Output is correct |
61 |
Correct |
15 ms |
1236 KB |
Output is correct |
62 |
Correct |
11 ms |
1240 KB |
Output is correct |
63 |
Correct |
13 ms |
1228 KB |
Output is correct |
64 |
Correct |
13 ms |
1228 KB |
Output is correct |
65 |
Correct |
22 ms |
1308 KB |
Output is correct |
66 |
Correct |
21 ms |
1228 KB |
Output is correct |
67 |
Correct |
24 ms |
1256 KB |
Output is correct |
68 |
Correct |
18 ms |
1280 KB |
Output is correct |
69 |
Correct |
16 ms |
1224 KB |
Output is correct |
70 |
Correct |
18 ms |
1252 KB |
Output is correct |
71 |
Correct |
18 ms |
1236 KB |
Output is correct |
72 |
Correct |
11 ms |
1228 KB |
Output is correct |
73 |
Correct |
20 ms |
1224 KB |
Output is correct |
74 |
Correct |
2 ms |
1228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
452 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
328 KB |
Output is correct |
29 |
Correct |
1 ms |
328 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
336 KB |
Output is correct |
38 |
Correct |
22 ms |
1216 KB |
Output is correct |
39 |
Correct |
24 ms |
1228 KB |
Output is correct |
40 |
Correct |
12 ms |
1244 KB |
Output is correct |
41 |
Correct |
14 ms |
1220 KB |
Output is correct |
42 |
Correct |
7 ms |
1244 KB |
Output is correct |
43 |
Correct |
12 ms |
1192 KB |
Output is correct |
44 |
Correct |
21 ms |
1200 KB |
Output is correct |
45 |
Correct |
23 ms |
1256 KB |
Output is correct |
46 |
Correct |
23 ms |
1272 KB |
Output is correct |
47 |
Correct |
24 ms |
1244 KB |
Output is correct |
48 |
Correct |
22 ms |
1208 KB |
Output is correct |
49 |
Correct |
17 ms |
1356 KB |
Output is correct |
50 |
Correct |
18 ms |
1260 KB |
Output is correct |
51 |
Correct |
16 ms |
1252 KB |
Output is correct |
52 |
Correct |
14 ms |
1220 KB |
Output is correct |
53 |
Correct |
15 ms |
1244 KB |
Output is correct |
54 |
Correct |
10 ms |
1228 KB |
Output is correct |
55 |
Correct |
7 ms |
1236 KB |
Output is correct |
56 |
Correct |
7 ms |
1228 KB |
Output is correct |
57 |
Correct |
9 ms |
1100 KB |
Output is correct |
58 |
Correct |
8 ms |
1228 KB |
Output is correct |
59 |
Correct |
14 ms |
1208 KB |
Output is correct |
60 |
Correct |
22 ms |
1236 KB |
Output is correct |
61 |
Correct |
15 ms |
1236 KB |
Output is correct |
62 |
Correct |
11 ms |
1240 KB |
Output is correct |
63 |
Correct |
13 ms |
1228 KB |
Output is correct |
64 |
Correct |
13 ms |
1228 KB |
Output is correct |
65 |
Correct |
22 ms |
1308 KB |
Output is correct |
66 |
Correct |
21 ms |
1228 KB |
Output is correct |
67 |
Correct |
24 ms |
1256 KB |
Output is correct |
68 |
Correct |
18 ms |
1280 KB |
Output is correct |
69 |
Correct |
16 ms |
1224 KB |
Output is correct |
70 |
Correct |
18 ms |
1252 KB |
Output is correct |
71 |
Correct |
18 ms |
1236 KB |
Output is correct |
72 |
Correct |
11 ms |
1228 KB |
Output is correct |
73 |
Correct |
20 ms |
1224 KB |
Output is correct |
74 |
Correct |
2 ms |
1228 KB |
Output is correct |
75 |
Execution timed out |
4067 ms |
122028 KB |
Time limit exceeded |
76 |
Halted |
0 ms |
0 KB |
- |