# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
796568 |
2023-07-28T14:05:13 Z |
thimote75 |
Cake 3 (JOI19_cake3) |
C++14 |
|
930 ms |
230392 KB |
#include <bits/stdc++.h>
#define int long long
#define p_be second
#define p_ta first
using namespace std;
using idata = vector<int>;
using t_perle = pair<int, int>;
using t_perles = vector<t_perle>;
struct WaveletTree {
WaveletTree* left_tree = nullptr;
WaveletTree* right_tree = nullptr;
int size;
idata values;
idata cumul;
idata target_pos_left;
idata target_pos_right;
WaveletTree (idata local_values, idata sorted_values) {
size = local_values.size();
values = local_values;
cumul.resize(local_values.size() + 1);
for (int i = 0; i < size; i ++)
cumul[i + 1] = cumul[i] + local_values[i];
int pivot;
if (sorted_values.size() == 1)
pivot = sorted_values[0];
else
pivot = sorted_values[(sorted_values.size() - 1) >> 1];
target_pos_left .resize(size, 0);
target_pos_right.resize(size, 0);
idata left_values;
idata left_values_sorted;
idata right_values;
idata right_values_sorted;
for (int i = 0; i < local_values.size(); i ++) {
int u = local_values[i];
if (u <= pivot) {
left_values.push_back(u);
target_pos_left[i] ++;
} else {
right_values.push_back(u);
target_pos_right[i] ++;
}
}
for (int i = 1; i < size; i ++) {
target_pos_right[i] += target_pos_right[i - 1];
target_pos_left [i] += target_pos_left [i - 1];
}
for (int u : sorted_values) {
if (u <= pivot) left_values_sorted.push_back(u);
else right_values_sorted.push_back(u);
}
if (right_values.size() == 0) return ;
left_tree = new WaveletTree(left_values, left_values_sorted);
right_tree = new WaveletTree(right_values, right_values_sorted);
}
int sumQuery (int M, int left, int right) {
return _sumQuery(M, left, right).second;
}
pair<int, int> _sumQuery (int M, int left, int right) {
if (M < 0) {
cout << "ERROR\n";
exit(0);
}
if (left < 0 || right >= size) {
cout << "ERROR\n";
exit(0);
}
if (M == 0) return { 0, 0 };
if (right - left + 1 <= M)
return { right - left + 1, cumul[right + 1] - cumul[left] };
if (right_tree == nullptr)
return { M, cumul[M] };
pair<int, int> right_result
= right_tree->_sumQuery(
M,
left == 0 ? 0 : target_pos_right[left - 1],
target_pos_right[right] - 1
);
if (M == right_result.first) return right_result;
pair<int, int> left_result
= left_tree->_sumQuery(
M - right_result.first,
left == 0 ? 0 : target_pos_left[left - 1],
target_pos_left[right] - 1
);
return {
left_result.first + right_result.first,
left_result.second + right_result.second
};
}
void show (int depth, int left, int right) {
if (depth <= 0 || left_tree == nullptr) {
cout << "[";
for (int i = 0; i < size; i ++) {
if (left <= i && i <= right)
cout << values[i] << ":" << cumul[i + 1] << ":" << target_pos_left[i] << ":" << target_pos_right[i];
else cout << "-:-:-:-";
if (i + 1 != size)
cout << ", ";
}
cout << "]";
return ;
}
left_tree ->show(depth - 1, left == 0 ? 0 : target_pos_left [left - 1], target_pos_left [right] - 1);
right_tree->show(depth - 1, left == 0 ? 0 : target_pos_right[left - 1], target_pos_right[right] - 1);
}
void del () {
if (left_tree) left_tree->del();
if (right_tree) right_tree->del();
delete left_tree;
delete right_tree;
}
};
int N, M;
int solve (WaveletTree &queryTree, t_perles &perles,
int left, int right, int opta, int optb) {
if (left == right) return -1e18;
int mid = (left + right) >> 1;
int optm = -1;
int optv = -1e18;
for (int opti = opta; opti <= optb; opti ++) {
if (opti + M - 1 > mid) break ;
int locv = queryTree.sumQuery( M - 2, opti + 1, mid - 1 ) + 2 * (perles[opti].p_ta - perles[mid].p_ta)
+ perles[opti].p_be + perles[mid].p_be;
if (locv <= optv) continue ;
optm = opti;
optv = locv;
}
if (left + 1 == right)
return optv;
int l_optv = solve(queryTree, perles, left, mid, opta, optm);
int r_optv = solve(queryTree, perles, mid + 1, right, optm, optb);
int o_optv = max(l_optv, r_optv);
return max(optv, o_optv);
}
signed main () {
cin >> N >> M;
t_perles perles;
set<int> beauty_set;
for (int i = 0; i < N; i ++) {
int b, t;
cin >> b >> t;
beauty_set.insert(b);
perles.push_back({ t, b });
}
idata beauty_unique;
for (int u : beauty_set) beauty_unique.push_back(u);
sort(perles.begin(), perles.end());
idata beauty;
for (const auto &perle : perles)
beauty.push_back(perle.p_be);
WaveletTree queryTree (beauty, beauty_unique);
cout << solve(queryTree, perles, M - 1, N, 0, N - 1) << endl;
queryTree.del();
}
Compilation message
cake3.cpp: In constructor 'WaveletTree::WaveletTree(idata, idata)':
cake3.cpp:45:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < local_values.size(); i ++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
0 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
0 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
276 KB |
Output is correct |
38 |
Correct |
5 ms |
2004 KB |
Output is correct |
39 |
Correct |
5 ms |
2004 KB |
Output is correct |
40 |
Correct |
4 ms |
2004 KB |
Output is correct |
41 |
Correct |
4 ms |
1876 KB |
Output is correct |
42 |
Correct |
4 ms |
2004 KB |
Output is correct |
43 |
Correct |
4 ms |
1876 KB |
Output is correct |
44 |
Correct |
5 ms |
1876 KB |
Output is correct |
45 |
Correct |
5 ms |
2004 KB |
Output is correct |
46 |
Correct |
7 ms |
2132 KB |
Output is correct |
47 |
Correct |
5 ms |
2004 KB |
Output is correct |
48 |
Correct |
7 ms |
1880 KB |
Output is correct |
49 |
Correct |
5 ms |
2004 KB |
Output is correct |
50 |
Correct |
5 ms |
2004 KB |
Output is correct |
51 |
Correct |
4 ms |
2004 KB |
Output is correct |
52 |
Correct |
4 ms |
2004 KB |
Output is correct |
53 |
Correct |
5 ms |
2004 KB |
Output is correct |
54 |
Correct |
4 ms |
2108 KB |
Output is correct |
55 |
Correct |
4 ms |
2004 KB |
Output is correct |
56 |
Correct |
4 ms |
2004 KB |
Output is correct |
57 |
Correct |
4 ms |
2004 KB |
Output is correct |
58 |
Correct |
4 ms |
2004 KB |
Output is correct |
59 |
Correct |
2 ms |
340 KB |
Output is correct |
60 |
Correct |
2 ms |
488 KB |
Output is correct |
61 |
Correct |
2 ms |
340 KB |
Output is correct |
62 |
Correct |
2 ms |
340 KB |
Output is correct |
63 |
Correct |
2 ms |
468 KB |
Output is correct |
64 |
Correct |
1 ms |
340 KB |
Output is correct |
65 |
Correct |
5 ms |
1940 KB |
Output is correct |
66 |
Correct |
5 ms |
1876 KB |
Output is correct |
67 |
Correct |
5 ms |
1984 KB |
Output is correct |
68 |
Correct |
5 ms |
2004 KB |
Output is correct |
69 |
Correct |
5 ms |
1876 KB |
Output is correct |
70 |
Correct |
4 ms |
1876 KB |
Output is correct |
71 |
Correct |
2 ms |
596 KB |
Output is correct |
72 |
Correct |
2 ms |
596 KB |
Output is correct |
73 |
Correct |
4 ms |
2004 KB |
Output is correct |
74 |
Correct |
4 ms |
2132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
0 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
276 KB |
Output is correct |
38 |
Correct |
5 ms |
2004 KB |
Output is correct |
39 |
Correct |
5 ms |
2004 KB |
Output is correct |
40 |
Correct |
4 ms |
2004 KB |
Output is correct |
41 |
Correct |
4 ms |
1876 KB |
Output is correct |
42 |
Correct |
4 ms |
2004 KB |
Output is correct |
43 |
Correct |
4 ms |
1876 KB |
Output is correct |
44 |
Correct |
5 ms |
1876 KB |
Output is correct |
45 |
Correct |
5 ms |
2004 KB |
Output is correct |
46 |
Correct |
7 ms |
2132 KB |
Output is correct |
47 |
Correct |
5 ms |
2004 KB |
Output is correct |
48 |
Correct |
7 ms |
1880 KB |
Output is correct |
49 |
Correct |
5 ms |
2004 KB |
Output is correct |
50 |
Correct |
5 ms |
2004 KB |
Output is correct |
51 |
Correct |
4 ms |
2004 KB |
Output is correct |
52 |
Correct |
4 ms |
2004 KB |
Output is correct |
53 |
Correct |
5 ms |
2004 KB |
Output is correct |
54 |
Correct |
4 ms |
2108 KB |
Output is correct |
55 |
Correct |
4 ms |
2004 KB |
Output is correct |
56 |
Correct |
4 ms |
2004 KB |
Output is correct |
57 |
Correct |
4 ms |
2004 KB |
Output is correct |
58 |
Correct |
4 ms |
2004 KB |
Output is correct |
59 |
Correct |
2 ms |
340 KB |
Output is correct |
60 |
Correct |
2 ms |
488 KB |
Output is correct |
61 |
Correct |
2 ms |
340 KB |
Output is correct |
62 |
Correct |
2 ms |
340 KB |
Output is correct |
63 |
Correct |
2 ms |
468 KB |
Output is correct |
64 |
Correct |
1 ms |
340 KB |
Output is correct |
65 |
Correct |
5 ms |
1940 KB |
Output is correct |
66 |
Correct |
5 ms |
1876 KB |
Output is correct |
67 |
Correct |
5 ms |
1984 KB |
Output is correct |
68 |
Correct |
5 ms |
2004 KB |
Output is correct |
69 |
Correct |
5 ms |
1876 KB |
Output is correct |
70 |
Correct |
4 ms |
1876 KB |
Output is correct |
71 |
Correct |
2 ms |
596 KB |
Output is correct |
72 |
Correct |
2 ms |
596 KB |
Output is correct |
73 |
Correct |
4 ms |
2004 KB |
Output is correct |
74 |
Correct |
4 ms |
2132 KB |
Output is correct |
75 |
Correct |
828 ms |
209904 KB |
Output is correct |
76 |
Correct |
930 ms |
207932 KB |
Output is correct |
77 |
Correct |
777 ms |
214044 KB |
Output is correct |
78 |
Correct |
839 ms |
217512 KB |
Output is correct |
79 |
Correct |
447 ms |
218208 KB |
Output is correct |
80 |
Correct |
467 ms |
211876 KB |
Output is correct |
81 |
Correct |
450 ms |
119540 KB |
Output is correct |
82 |
Correct |
567 ms |
134360 KB |
Output is correct |
83 |
Correct |
514 ms |
127292 KB |
Output is correct |
84 |
Correct |
563 ms |
130100 KB |
Output is correct |
85 |
Correct |
457 ms |
121336 KB |
Output is correct |
86 |
Correct |
316 ms |
109796 KB |
Output is correct |
87 |
Correct |
348 ms |
110088 KB |
Output is correct |
88 |
Correct |
405 ms |
114264 KB |
Output is correct |
89 |
Correct |
405 ms |
116704 KB |
Output is correct |
90 |
Correct |
333 ms |
116608 KB |
Output is correct |
91 |
Correct |
264 ms |
106156 KB |
Output is correct |
92 |
Correct |
278 ms |
105860 KB |
Output is correct |
93 |
Correct |
285 ms |
110360 KB |
Output is correct |
94 |
Correct |
248 ms |
111972 KB |
Output is correct |
95 |
Correct |
338 ms |
115912 KB |
Output is correct |
96 |
Correct |
105 ms |
18156 KB |
Output is correct |
97 |
Correct |
114 ms |
19676 KB |
Output is correct |
98 |
Correct |
113 ms |
19140 KB |
Output is correct |
99 |
Correct |
111 ms |
19376 KB |
Output is correct |
100 |
Correct |
103 ms |
18220 KB |
Output is correct |
101 |
Correct |
102 ms |
18220 KB |
Output is correct |
102 |
Correct |
323 ms |
90348 KB |
Output is correct |
103 |
Correct |
324 ms |
89004 KB |
Output is correct |
104 |
Correct |
362 ms |
95988 KB |
Output is correct |
105 |
Correct |
282 ms |
88416 KB |
Output is correct |
106 |
Correct |
313 ms |
91656 KB |
Output is correct |
107 |
Correct |
271 ms |
86364 KB |
Output is correct |
108 |
Correct |
863 ms |
216356 KB |
Output is correct |
109 |
Correct |
772 ms |
229628 KB |
Output is correct |
110 |
Correct |
129 ms |
39160 KB |
Output is correct |
111 |
Correct |
153 ms |
39036 KB |
Output is correct |
112 |
Correct |
515 ms |
205572 KB |
Output is correct |
113 |
Correct |
492 ms |
230392 KB |
Output is correct |