#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)
const int N = 5e5 + 5;
int n;
int bit[N], c[N];
vector <pair<int,int>> pos[N];
void upd(int x, int val){
for(; x < N; x = (x|(x+1))) bit[x] += val;
}
int sum(int x){
int res = 0;
for(; x >= 0; x = (x&(x+1)) - 1) res += bit[x];
return res;
}
int get(int x){
int l = 1, r = n;
while(l < r){
int m = (l+r)>>1;
if(sum(m) >= x) r = m;
else l = m+1;
}
return c[l];
}
int subtask_2(vector <int> A){
int ans = 1;
f(i,0,n){
c[A[i]]++;
upd(A[i], 1);
f(j,i,n){
int l = j - i + 1;
if(l&1){
ans = max(ans, get((l+1)/2));
}
else{
ans = max(ans, get(l/2));
ans = max(ans, get(l/2 + 1));
}
if(j+1 < n) {
c[A[j+1]]++;
upd(A[j+1], 1);
}
}
f(j,i,n){
c[A[j]]--;
upd(A[j], -1);
}
}
return ans;
}
int id(int pos){
if(pos == 0) return 0;
if(c[1] >= pos) return 1;
if(c[1] + c[2] >= pos) return 2;
return 3;
}
int res(vector <int> v){
vector <int> aux, mini;
int len = v.size(), ans = 1;
f(i,0,len) {
aux.push_back(v[i] - 2*i);
mini.push_back(v[i] - 2*i);
}
fa(i,len-2,0) mini[i] = min(mini[i+1], mini[i]);
f(i,0,len-1){
int ult = aux[i] + 1; // <= ult
if(mini[i+1] > ult) continue;
int l = i+1, r = len-1;
while(l < r){
int m = (l+r+1)>>1;
if(mini[m] > ult) r = m-1;
else l = m;
}
ans = max(ans, l-i+1);
}
return ans;
}
int subtask_4(vector <int> A){
for(int x: A) c[x]++;
int p1 = 0, p2 = 0;
if(n&1) p1 = (n+1)/2;
else p1 = n/2, p2 = p1 + 1;
if(id(p1) == 1 or id(p1) == 3) return c[id(p1)];
if(id(p2) == 1 or id(p2) == 3) return c[id(p2)];
if(c[2] > c[1] and c[2] > c[3]) return c[2];
int ans = c[2];
vector <int> P1, P3;
f(i,0,n){
if(A[i] == 1) P1.push_back(i);
if(A[i] == 3) P3.push_back(i);
}
ans = max(ans, res(P1));
ans = max(ans, res(P3));
return ans;
}
bool is(int l, int r, int ty){
if(l > r) return 0;
if(l != r) return 1;
return l%2 == ty;
}
int subtask_3(vector <int> A){
int ans = 0, id = 0;
while(id < n){
int c = 0, ini = id+1, comp = A[id];
while(A[id] == comp and id < n) c++, id++;
ans = max(ans, c);
pos[comp].push_back({ini, ini + c - 1});
}
f(i,1,n+1){
if(pos[i].size() != 2) continue;
int l1 = pos[i][0].first, r1 = pos[i][0].second;
int l2 = pos[i][1].first, r2 = pos[i][1].second;
int C = r1 - l1 + r2 - l2 + 2;
int B = -(r1 + 1) + (l2 - 1) + 1;
int A = n - C - B, ty = (B+C)%2;
bool fe = 0;
if(is(max(0, B-C), min(A, B+C), ty)) fe = 1;
if(is(max(0, B-C-1), min(A, B+C-1), 1-ty)) fe = 1;
if(fe) ans = max(ans, C);
}
return ans;
}
int sequence(int Ni, vector<int> A) {
n = Ni;
if(n <= 2000) return subtask_2(A);
int maxi = 0;
for(int x: A) maxi = max(maxi, x);
if(maxi <= 3) return subtask_4(A);
return subtask_3(A);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
12016 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
5 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
11988 KB |
Output is correct |
10 |
Correct |
6 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11972 KB |
Output is correct |
12 |
Correct |
6 ms |
11988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
12016 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
5 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
11988 KB |
Output is correct |
10 |
Correct |
6 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11972 KB |
Output is correct |
12 |
Correct |
6 ms |
11988 KB |
Output is correct |
13 |
Correct |
256 ms |
12116 KB |
Output is correct |
14 |
Correct |
267 ms |
12116 KB |
Output is correct |
15 |
Correct |
203 ms |
12116 KB |
Output is correct |
16 |
Correct |
204 ms |
12092 KB |
Output is correct |
17 |
Correct |
221 ms |
12092 KB |
Output is correct |
18 |
Correct |
321 ms |
12116 KB |
Output is correct |
19 |
Correct |
261 ms |
12116 KB |
Output is correct |
20 |
Correct |
214 ms |
12116 KB |
Output is correct |
21 |
Correct |
270 ms |
12116 KB |
Output is correct |
22 |
Correct |
253 ms |
12104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
60 ms |
27700 KB |
Output is correct |
3 |
Correct |
138 ms |
27760 KB |
Output is correct |
4 |
Correct |
66 ms |
17836 KB |
Output is correct |
5 |
Correct |
101 ms |
26804 KB |
Output is correct |
6 |
Correct |
61 ms |
26752 KB |
Output is correct |
7 |
Correct |
57 ms |
17836 KB |
Output is correct |
8 |
Correct |
54 ms |
17836 KB |
Output is correct |
9 |
Correct |
47 ms |
17868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
43 ms |
17840 KB |
Output is correct |
3 |
Correct |
55 ms |
22556 KB |
Output is correct |
4 |
Correct |
38 ms |
17852 KB |
Output is correct |
5 |
Correct |
40 ms |
17848 KB |
Output is correct |
6 |
Correct |
62 ms |
24172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
87 ms |
33456 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
12016 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
5 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
11988 KB |
Output is correct |
10 |
Correct |
6 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11972 KB |
Output is correct |
12 |
Correct |
6 ms |
11988 KB |
Output is correct |
13 |
Correct |
256 ms |
12116 KB |
Output is correct |
14 |
Correct |
267 ms |
12116 KB |
Output is correct |
15 |
Correct |
203 ms |
12116 KB |
Output is correct |
16 |
Correct |
204 ms |
12092 KB |
Output is correct |
17 |
Correct |
221 ms |
12092 KB |
Output is correct |
18 |
Correct |
321 ms |
12116 KB |
Output is correct |
19 |
Correct |
261 ms |
12116 KB |
Output is correct |
20 |
Correct |
214 ms |
12116 KB |
Output is correct |
21 |
Correct |
270 ms |
12116 KB |
Output is correct |
22 |
Correct |
253 ms |
12104 KB |
Output is correct |
23 |
Incorrect |
17 ms |
14676 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
12016 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
5 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
11988 KB |
Output is correct |
10 |
Correct |
6 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11972 KB |
Output is correct |
12 |
Correct |
6 ms |
11988 KB |
Output is correct |
13 |
Correct |
256 ms |
12116 KB |
Output is correct |
14 |
Correct |
267 ms |
12116 KB |
Output is correct |
15 |
Correct |
203 ms |
12116 KB |
Output is correct |
16 |
Correct |
204 ms |
12092 KB |
Output is correct |
17 |
Correct |
221 ms |
12092 KB |
Output is correct |
18 |
Correct |
321 ms |
12116 KB |
Output is correct |
19 |
Correct |
261 ms |
12116 KB |
Output is correct |
20 |
Correct |
214 ms |
12116 KB |
Output is correct |
21 |
Correct |
270 ms |
12116 KB |
Output is correct |
22 |
Correct |
253 ms |
12104 KB |
Output is correct |
23 |
Correct |
60 ms |
27700 KB |
Output is correct |
24 |
Correct |
138 ms |
27760 KB |
Output is correct |
25 |
Correct |
66 ms |
17836 KB |
Output is correct |
26 |
Correct |
101 ms |
26804 KB |
Output is correct |
27 |
Correct |
61 ms |
26752 KB |
Output is correct |
28 |
Correct |
57 ms |
17836 KB |
Output is correct |
29 |
Correct |
54 ms |
17836 KB |
Output is correct |
30 |
Correct |
47 ms |
17868 KB |
Output is correct |
31 |
Correct |
43 ms |
17840 KB |
Output is correct |
32 |
Correct |
55 ms |
22556 KB |
Output is correct |
33 |
Correct |
38 ms |
17852 KB |
Output is correct |
34 |
Correct |
40 ms |
17848 KB |
Output is correct |
35 |
Correct |
62 ms |
24172 KB |
Output is correct |
36 |
Incorrect |
87 ms |
33456 KB |
Output isn't correct |
37 |
Halted |
0 ms |
0 KB |
- |