# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
826148 |
2023-08-15T10:42:15 Z |
KoD |
Sequence (APIO23_sequence) |
C++17 |
|
635 ms |
43340 KB |
#include "sequence.h"
#include <algorithm>
#include <utility>
#include <vector>
using std::pair;
using std::vector;
struct node {
int min, max, sum;
static node id() { return {0, 0, 0}; }
static node one(int x) { return {std::min(x, 0), std::max(x, 0), x}; }
node operator+(const node& n) const { return node(*this) += n; }
node& operator+=(const node& n) {
min = std::min(min, n.min + sum);
max = std::max(max, n.max + sum);
sum += n.sum;
return *this;
}
};
struct segment_tree {
explicit segment_tree(int n, const node& x) : size(n), data(2 * n, x) {
for (int i = n - 1; i > 0; --i) fetch(i);
}
void set(int i, const node& n) {
i += size;
data[i] = n;
while (i >>= 1) fetch(i);
}
int sum(int l, int r) const {
l += size, r += size;
int ret = 0;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) ret += data[l++].sum;
if (r & 1) ret += data[--r].sum;
}
return ret;
}
node fold(int l, int r) const {
l += size, r += size;
node ret_l = node::id(), ret_r = node::id();
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) ret_l += data[l++];
if (r & 1) ret_r = data[--r] + ret_r;
}
return ret_l + ret_r;
}
private:
int size;
vector<node> data;
void fetch(int i) { data[i] = data[2 * i + 0] + data[2 * i + 1]; }
};
int sequence(int N, vector<int> A) {
vector<vector<int>> C(N);
for (int i = 0; i < N; ++i) {
A[i] -= 1;
C[A[i]].push_back(i);
}
int ret = 0;
for (int i = 0, j = 0; i < N; ++i) {
const int c = (int)C[i].size();
if (j <= N / 2 && N / 2 < j + c) ret = std::max(ret, c);
j += c;
}
for (int phase = 0; phase < 2; ++phase) {
segment_tree seg(N, node::one(-1));
for (int x = 0; x < N; ++x) {
const auto& v = C[x];
const int n = (int)v.size();
for (const int i : v) seg.set(i, node::one(+1));
if (n <= ret) continue;
for (int i = 0, j = 0; i < n; ++i) {
const auto [l0, r0, $0] = seg.fold(0, v[i]);
while (j < n) {
const int offset = seg.sum(0, v[j] + 1);
const auto [l1, r1, $1] = seg.fold(v[j] + 1, N);
if (std::max(l0, l1 + offset) > std::min(r0, r1 + offset)) break;
j += 1;
}
ret = std::max(ret, j - i);
}
}
std::reverse(C.begin(), C.end());
}
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 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 |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
153 ms |
37572 KB |
Output is correct |
3 |
Correct |
157 ms |
37604 KB |
Output is correct |
4 |
Correct |
261 ms |
29884 KB |
Output is correct |
5 |
Correct |
147 ms |
36664 KB |
Output is correct |
6 |
Correct |
147 ms |
36668 KB |
Output is correct |
7 |
Correct |
174 ms |
30084 KB |
Output is correct |
8 |
Correct |
243 ms |
30284 KB |
Output is correct |
9 |
Correct |
235 ms |
29768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
136 ms |
29920 KB |
Output is correct |
3 |
Correct |
364 ms |
29732 KB |
Output is correct |
4 |
Correct |
119 ms |
29740 KB |
Output is correct |
5 |
Correct |
118 ms |
29856 KB |
Output is correct |
6 |
Correct |
437 ms |
29876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
255 ms |
43336 KB |
Output is correct |
2 |
Correct |
270 ms |
43320 KB |
Output is correct |
3 |
Correct |
277 ms |
42756 KB |
Output is correct |
4 |
Correct |
267 ms |
42752 KB |
Output is correct |
5 |
Correct |
269 ms |
39428 KB |
Output is correct |
6 |
Correct |
340 ms |
39400 KB |
Output is correct |
7 |
Correct |
337 ms |
38224 KB |
Output is correct |
8 |
Correct |
187 ms |
37840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 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 |
340 KB |
Output is correct |
23 |
Correct |
28 ms |
6280 KB |
Output is correct |
24 |
Correct |
30 ms |
6272 KB |
Output is correct |
25 |
Correct |
32 ms |
6244 KB |
Output is correct |
26 |
Correct |
21 ms |
5332 KB |
Output is correct |
27 |
Correct |
21 ms |
5332 KB |
Output is correct |
28 |
Correct |
66 ms |
5324 KB |
Output is correct |
29 |
Correct |
64 ms |
5080 KB |
Output is correct |
30 |
Correct |
39 ms |
5132 KB |
Output is correct |
31 |
Correct |
18 ms |
5068 KB |
Output is correct |
32 |
Correct |
21 ms |
7184 KB |
Output is correct |
33 |
Correct |
28 ms |
6080 KB |
Output is correct |
34 |
Correct |
32 ms |
6016 KB |
Output is correct |
35 |
Correct |
31 ms |
6036 KB |
Output is correct |
36 |
Correct |
33 ms |
5964 KB |
Output is correct |
37 |
Correct |
32 ms |
6036 KB |
Output is correct |
38 |
Correct |
37 ms |
6100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 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 |
340 KB |
Output is correct |
23 |
Correct |
153 ms |
37572 KB |
Output is correct |
24 |
Correct |
157 ms |
37604 KB |
Output is correct |
25 |
Correct |
261 ms |
29884 KB |
Output is correct |
26 |
Correct |
147 ms |
36664 KB |
Output is correct |
27 |
Correct |
147 ms |
36668 KB |
Output is correct |
28 |
Correct |
174 ms |
30084 KB |
Output is correct |
29 |
Correct |
243 ms |
30284 KB |
Output is correct |
30 |
Correct |
235 ms |
29768 KB |
Output is correct |
31 |
Correct |
136 ms |
29920 KB |
Output is correct |
32 |
Correct |
364 ms |
29732 KB |
Output is correct |
33 |
Correct |
119 ms |
29740 KB |
Output is correct |
34 |
Correct |
118 ms |
29856 KB |
Output is correct |
35 |
Correct |
437 ms |
29876 KB |
Output is correct |
36 |
Correct |
255 ms |
43336 KB |
Output is correct |
37 |
Correct |
270 ms |
43320 KB |
Output is correct |
38 |
Correct |
277 ms |
42756 KB |
Output is correct |
39 |
Correct |
267 ms |
42752 KB |
Output is correct |
40 |
Correct |
269 ms |
39428 KB |
Output is correct |
41 |
Correct |
340 ms |
39400 KB |
Output is correct |
42 |
Correct |
337 ms |
38224 KB |
Output is correct |
43 |
Correct |
187 ms |
37840 KB |
Output is correct |
44 |
Correct |
28 ms |
6280 KB |
Output is correct |
45 |
Correct |
30 ms |
6272 KB |
Output is correct |
46 |
Correct |
32 ms |
6244 KB |
Output is correct |
47 |
Correct |
21 ms |
5332 KB |
Output is correct |
48 |
Correct |
21 ms |
5332 KB |
Output is correct |
49 |
Correct |
66 ms |
5324 KB |
Output is correct |
50 |
Correct |
64 ms |
5080 KB |
Output is correct |
51 |
Correct |
39 ms |
5132 KB |
Output is correct |
52 |
Correct |
18 ms |
5068 KB |
Output is correct |
53 |
Correct |
21 ms |
7184 KB |
Output is correct |
54 |
Correct |
28 ms |
6080 KB |
Output is correct |
55 |
Correct |
32 ms |
6016 KB |
Output is correct |
56 |
Correct |
31 ms |
6036 KB |
Output is correct |
57 |
Correct |
33 ms |
5964 KB |
Output is correct |
58 |
Correct |
32 ms |
6036 KB |
Output is correct |
59 |
Correct |
37 ms |
6100 KB |
Output is correct |
60 |
Correct |
385 ms |
37640 KB |
Output is correct |
61 |
Correct |
356 ms |
37540 KB |
Output is correct |
62 |
Correct |
343 ms |
37688 KB |
Output is correct |
63 |
Correct |
485 ms |
30816 KB |
Output is correct |
64 |
Correct |
583 ms |
30884 KB |
Output is correct |
65 |
Correct |
635 ms |
30892 KB |
Output is correct |
66 |
Correct |
408 ms |
29920 KB |
Output is correct |
67 |
Correct |
197 ms |
30164 KB |
Output is correct |
68 |
Correct |
124 ms |
29748 KB |
Output is correct |
69 |
Correct |
144 ms |
43340 KB |
Output is correct |
70 |
Correct |
363 ms |
36692 KB |
Output is correct |
71 |
Correct |
327 ms |
36544 KB |
Output is correct |
72 |
Correct |
339 ms |
36052 KB |
Output is correct |
73 |
Correct |
400 ms |
36304 KB |
Output is correct |
74 |
Correct |
352 ms |
35956 KB |
Output is correct |
75 |
Correct |
381 ms |
36464 KB |
Output is correct |