# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
947352 |
2024-03-16T01:58:36 Z |
caterpillow |
Cake 3 (JOI19_cake3) |
C++17 |
|
856 ms |
191364 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define F0R(i, b) FOR(i, 0, b)
#define endl '\n'
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
const ll INF = 1e18;
/*
as l increases, the optimal r also increases
*/
const int sz = 1 << 18;
using ptr = struct Node*;
struct Node {
ll val;
int cnt;
ptr l, r;
Node(ll _val, int _cnt) {
val = _val;
cnt = _cnt;
l = r = 0;
}
Node(ptr _l, ptr _r) {
l = _l;
r = _r;
val = cnt = 0;
if (l) val += l->val, cnt += l->cnt;
if (r) val += r->val, cnt += r->cnt;
}
};
ptr update(ptr n, ll val, int i, int l = 0, int r = sz - 1) {
if (l == r) return new Node(val, 1);
int m = (l + r) / 2;
if (i <= m) return new Node(update(n->l, val, i, l, m), n->r);
else return new Node(n->l, update(n->r, val, i, m + 1, r));
}
ll walk(ptr l, ptr r, int k, int lo = 0, int hi = sz - 1) { // sum of k largest
if (lo == hi) return r->val - l->val;
int m = (lo + hi) / 2;
int rhs = r->r->cnt - l->r->cnt;
if (rhs >= k) return walk(l->r, r->r, k, m + 1, hi);
else return walk(l->l, r->l, k - rhs, lo, m) + r->r->val - l->r->val;
}
ptr roots[sz];
int n, k;
vt<pl> cakes;
ll query(int l, int r) {
if (l > r) return 0ll;
return walk(roots[l], roots[r + 1], k - 2);
}
ll dnc(int l, int r, int lo, int hi) {
if (l > r) return -INF;
int m = (l + r) / 2;
pl best = {-INF, hi};
FOR (i, lo, hi + 1) {
if (i - m + 1 < k) continue;
ll val = query(m + 1, i - 1) - (cakes[i].f - cakes[m].f) + cakes[i].s + cakes[m].s;
best = max(best, pl{val, i});
}
return max({best.f, dnc(l, m - 1, lo, best.s), dnc(m + 1, r, best.s, hi)});
}
main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
cakes.resize(n); // colour, value
F0R (i, n) cin >> cakes[i].s >> cakes[i].f, cakes[i].f *= 2;
sort(all(cakes));
vt<pl> sorted(n);
F0R (i, n) sorted[i] = {cakes[i].s, i};
sort(all(sorted));
vt<int> rind(n);
F0R (i, n) rind[sorted[i].s] = i;
ptr root = new Node(0, 0);
roots[0] = root->l = root->r = root;
F0R (i, n) {
roots[i + 1] = update(roots[i], cakes[i].s, rind[i]);
}
cout << dnc(0, n - 1, 0, n - 1) << endl;
}
Compilation message
cake3.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
84 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
428 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
600 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
464 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
428 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
600 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
464 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
4 ms |
2140 KB |
Output is correct |
39 |
Correct |
4 ms |
2140 KB |
Output is correct |
40 |
Correct |
3 ms |
2140 KB |
Output is correct |
41 |
Correct |
3 ms |
2140 KB |
Output is correct |
42 |
Correct |
3 ms |
2140 KB |
Output is correct |
43 |
Correct |
3 ms |
2008 KB |
Output is correct |
44 |
Correct |
3 ms |
2140 KB |
Output is correct |
45 |
Correct |
3 ms |
2288 KB |
Output is correct |
46 |
Correct |
3 ms |
2264 KB |
Output is correct |
47 |
Correct |
4 ms |
2140 KB |
Output is correct |
48 |
Correct |
3 ms |
2140 KB |
Output is correct |
49 |
Correct |
3 ms |
2140 KB |
Output is correct |
50 |
Correct |
3 ms |
2140 KB |
Output is correct |
51 |
Correct |
3 ms |
2064 KB |
Output is correct |
52 |
Correct |
3 ms |
2136 KB |
Output is correct |
53 |
Correct |
3 ms |
2072 KB |
Output is correct |
54 |
Correct |
3 ms |
2140 KB |
Output is correct |
55 |
Correct |
2 ms |
2140 KB |
Output is correct |
56 |
Correct |
2 ms |
2140 KB |
Output is correct |
57 |
Correct |
2 ms |
2140 KB |
Output is correct |
58 |
Correct |
2 ms |
2140 KB |
Output is correct |
59 |
Correct |
3 ms |
2140 KB |
Output is correct |
60 |
Correct |
5 ms |
2268 KB |
Output is correct |
61 |
Correct |
3 ms |
2140 KB |
Output is correct |
62 |
Correct |
3 ms |
2140 KB |
Output is correct |
63 |
Correct |
3 ms |
2140 KB |
Output is correct |
64 |
Correct |
3 ms |
2268 KB |
Output is correct |
65 |
Correct |
3 ms |
2140 KB |
Output is correct |
66 |
Correct |
3 ms |
2136 KB |
Output is correct |
67 |
Correct |
3 ms |
2136 KB |
Output is correct |
68 |
Correct |
3 ms |
2240 KB |
Output is correct |
69 |
Correct |
3 ms |
2140 KB |
Output is correct |
70 |
Correct |
3 ms |
2136 KB |
Output is correct |
71 |
Correct |
4 ms |
2140 KB |
Output is correct |
72 |
Correct |
3 ms |
2264 KB |
Output is correct |
73 |
Correct |
3 ms |
2140 KB |
Output is correct |
74 |
Correct |
2 ms |
2140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
428 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
600 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
464 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
4 ms |
2140 KB |
Output is correct |
39 |
Correct |
4 ms |
2140 KB |
Output is correct |
40 |
Correct |
3 ms |
2140 KB |
Output is correct |
41 |
Correct |
3 ms |
2140 KB |
Output is correct |
42 |
Correct |
3 ms |
2140 KB |
Output is correct |
43 |
Correct |
3 ms |
2008 KB |
Output is correct |
44 |
Correct |
3 ms |
2140 KB |
Output is correct |
45 |
Correct |
3 ms |
2288 KB |
Output is correct |
46 |
Correct |
3 ms |
2264 KB |
Output is correct |
47 |
Correct |
4 ms |
2140 KB |
Output is correct |
48 |
Correct |
3 ms |
2140 KB |
Output is correct |
49 |
Correct |
3 ms |
2140 KB |
Output is correct |
50 |
Correct |
3 ms |
2140 KB |
Output is correct |
51 |
Correct |
3 ms |
2064 KB |
Output is correct |
52 |
Correct |
3 ms |
2136 KB |
Output is correct |
53 |
Correct |
3 ms |
2072 KB |
Output is correct |
54 |
Correct |
3 ms |
2140 KB |
Output is correct |
55 |
Correct |
2 ms |
2140 KB |
Output is correct |
56 |
Correct |
2 ms |
2140 KB |
Output is correct |
57 |
Correct |
2 ms |
2140 KB |
Output is correct |
58 |
Correct |
2 ms |
2140 KB |
Output is correct |
59 |
Correct |
3 ms |
2140 KB |
Output is correct |
60 |
Correct |
5 ms |
2268 KB |
Output is correct |
61 |
Correct |
3 ms |
2140 KB |
Output is correct |
62 |
Correct |
3 ms |
2140 KB |
Output is correct |
63 |
Correct |
3 ms |
2140 KB |
Output is correct |
64 |
Correct |
3 ms |
2268 KB |
Output is correct |
65 |
Correct |
3 ms |
2140 KB |
Output is correct |
66 |
Correct |
3 ms |
2136 KB |
Output is correct |
67 |
Correct |
3 ms |
2136 KB |
Output is correct |
68 |
Correct |
3 ms |
2240 KB |
Output is correct |
69 |
Correct |
3 ms |
2140 KB |
Output is correct |
70 |
Correct |
3 ms |
2136 KB |
Output is correct |
71 |
Correct |
4 ms |
2140 KB |
Output is correct |
72 |
Correct |
3 ms |
2264 KB |
Output is correct |
73 |
Correct |
3 ms |
2140 KB |
Output is correct |
74 |
Correct |
2 ms |
2140 KB |
Output is correct |
75 |
Correct |
806 ms |
178352 KB |
Output is correct |
76 |
Correct |
856 ms |
173864 KB |
Output is correct |
77 |
Correct |
719 ms |
178716 KB |
Output is correct |
78 |
Correct |
764 ms |
181396 KB |
Output is correct |
79 |
Correct |
271 ms |
181840 KB |
Output is correct |
80 |
Correct |
281 ms |
176724 KB |
Output is correct |
81 |
Correct |
547 ms |
179568 KB |
Output is correct |
82 |
Correct |
698 ms |
181984 KB |
Output is correct |
83 |
Correct |
645 ms |
187912 KB |
Output is correct |
84 |
Correct |
634 ms |
187472 KB |
Output is correct |
85 |
Correct |
559 ms |
180804 KB |
Output is correct |
86 |
Correct |
397 ms |
175108 KB |
Output is correct |
87 |
Correct |
400 ms |
172644 KB |
Output is correct |
88 |
Correct |
518 ms |
171728 KB |
Output is correct |
89 |
Correct |
533 ms |
181328 KB |
Output is correct |
90 |
Correct |
409 ms |
189096 KB |
Output is correct |
91 |
Correct |
359 ms |
175124 KB |
Output is correct |
92 |
Correct |
319 ms |
173852 KB |
Output is correct |
93 |
Correct |
369 ms |
181448 KB |
Output is correct |
94 |
Correct |
317 ms |
189012 KB |
Output is correct |
95 |
Correct |
406 ms |
189416 KB |
Output is correct |
96 |
Correct |
404 ms |
175956 KB |
Output is correct |
97 |
Correct |
432 ms |
189864 KB |
Output is correct |
98 |
Correct |
435 ms |
187148 KB |
Output is correct |
99 |
Correct |
390 ms |
187536 KB |
Output is correct |
100 |
Correct |
344 ms |
176932 KB |
Output is correct |
101 |
Correct |
360 ms |
176960 KB |
Output is correct |
102 |
Correct |
522 ms |
177236 KB |
Output is correct |
103 |
Correct |
498 ms |
174508 KB |
Output is correct |
104 |
Correct |
674 ms |
184372 KB |
Output is correct |
105 |
Correct |
523 ms |
183440 KB |
Output is correct |
106 |
Correct |
514 ms |
187984 KB |
Output is correct |
107 |
Correct |
440 ms |
181632 KB |
Output is correct |
108 |
Correct |
730 ms |
180392 KB |
Output is correct |
109 |
Correct |
645 ms |
191324 KB |
Output is correct |
110 |
Correct |
284 ms |
178000 KB |
Output is correct |
111 |
Correct |
358 ms |
179276 KB |
Output is correct |
112 |
Correct |
653 ms |
171280 KB |
Output is correct |
113 |
Correct |
295 ms |
191364 KB |
Output is correct |