#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
int sequence(int N, vector<int> A) {
if (N <= 2000) {
int ans = 1;
for (int i = 0; i < N; i++) {
vector<int> cnt(N+1, 0);
multiset<ari2> stuff;
cnt[A[i]]++;
stuff.insert({A[i], -i});
ari2 med = {A[i], -i};
for (int j = i+1; j < N; j++) {
stuff.insert({A[j], -j});
cnt[A[j]]++;
if (ari2{A[j], -j} < med && (j - i & 1)) {
med = *prev(stuff.find(med));
} else if (ari2{A[j], -j} > med && !(j - i & 1)) {
med = *next(stuff.find(med));
}
ans = max(ans, cnt[med[0]]);
if (j - i & 1) {
auto [a, b] = *next(stuff.find(med));
ans = max(ans, cnt[a]);
}
}
}
return ans;
}
int middle = max_element(A.begin(), A.end()) - A.begin();
bool mountain = true;
for (int i = middle - 1; i >= 0 && mountain; i--) {
mountain &= A[i] <= A[i+1];
}
for (int i = middle + 1; i < N && mountain; i++) {
mountain &= A[i] <= A[i-1];
}
if (mountain) {
vector<int> inds[N];
for (int i = 0; i < N; i++) {
inds[A[i]-1].push_back(i);
}
int ans = 0;
for (int ii = 0; ii < N; ii++) {
if (inds[ii].size() < 2) {
ans = max(ans, (int)inds[ii].size());
continue;
}
int l1 = inds[ii][0], r1 = -1, l2 = -1, r2 = inds[ii].back();
for (int i = 1; i < inds[ii].size(); i++) {
if (inds[ii][i-1]+1 < inds[ii][i]) {
r1 = inds[ii][i-1];
l2 = inds[ii][i];
break;
}
}
if (r1 < 0) {
ans = max(ans, r2 - l1 + 1);
} else {
int gap = l2 - r1 - 1;
if (gap > r1 - l1 + 1 + r2 - l2 + 1) {
if (l1 + N - r2 - 1 >= gap - (r1 - l1 + 1 + r2 - l2 + 1)) {
ans = max(ans, r1 - l1 + 1 + r2 - l2 + 1);
}
} else {
ans = max(ans, r1 - l1 + 1 + r2 - l2 + 1);
}
}
}
return ans;
}
}
Compilation message
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:18:36: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
18 | if (ari2{A[j], -j} < med && (j - i & 1)) {
| ~~^~~
sequence.cpp:20:44: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
20 | } else if (ari2{A[j], -j} > med && !(j - i & 1)) {
| ~~^~~
sequence.cpp:24:11: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
24 | if (j - i & 1) {
| ~~^~~
sequence.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 1; i < inds[ii].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
sequence.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
77 | }
| ^
# |
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 |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
2 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
2 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
430 ms |
392 KB |
Output is correct |
14 |
Correct |
417 ms |
388 KB |
Output is correct |
15 |
Correct |
425 ms |
392 KB |
Output is correct |
16 |
Correct |
417 ms |
460 KB |
Output is correct |
17 |
Correct |
421 ms |
392 KB |
Output is correct |
18 |
Correct |
341 ms |
340 KB |
Output is correct |
19 |
Correct |
442 ms |
392 KB |
Output is correct |
20 |
Correct |
453 ms |
388 KB |
Output is correct |
21 |
Correct |
431 ms |
392 KB |
Output is correct |
22 |
Correct |
429 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
82 ms |
25816 KB |
Output is correct |
3 |
Correct |
83 ms |
25804 KB |
Output is correct |
4 |
Correct |
45 ms |
17920 KB |
Output is correct |
5 |
Correct |
78 ms |
24872 KB |
Output is correct |
6 |
Correct |
81 ms |
24904 KB |
Output is correct |
7 |
Incorrect |
47 ms |
18388 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
46 ms |
18984 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
131 ms |
31688 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
2 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
430 ms |
392 KB |
Output is correct |
14 |
Correct |
417 ms |
388 KB |
Output is correct |
15 |
Correct |
425 ms |
392 KB |
Output is correct |
16 |
Correct |
417 ms |
460 KB |
Output is correct |
17 |
Correct |
421 ms |
392 KB |
Output is correct |
18 |
Correct |
341 ms |
340 KB |
Output is correct |
19 |
Correct |
442 ms |
392 KB |
Output is correct |
20 |
Correct |
453 ms |
388 KB |
Output is correct |
21 |
Correct |
431 ms |
392 KB |
Output is correct |
22 |
Correct |
429 ms |
340 KB |
Output is correct |
23 |
Incorrect |
15 ms |
4336 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
2 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
430 ms |
392 KB |
Output is correct |
14 |
Correct |
417 ms |
388 KB |
Output is correct |
15 |
Correct |
425 ms |
392 KB |
Output is correct |
16 |
Correct |
417 ms |
460 KB |
Output is correct |
17 |
Correct |
421 ms |
392 KB |
Output is correct |
18 |
Correct |
341 ms |
340 KB |
Output is correct |
19 |
Correct |
442 ms |
392 KB |
Output is correct |
20 |
Correct |
453 ms |
388 KB |
Output is correct |
21 |
Correct |
431 ms |
392 KB |
Output is correct |
22 |
Correct |
429 ms |
340 KB |
Output is correct |
23 |
Correct |
82 ms |
25816 KB |
Output is correct |
24 |
Correct |
83 ms |
25804 KB |
Output is correct |
25 |
Correct |
45 ms |
17920 KB |
Output is correct |
26 |
Correct |
78 ms |
24872 KB |
Output is correct |
27 |
Correct |
81 ms |
24904 KB |
Output is correct |
28 |
Incorrect |
47 ms |
18388 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |