#include "sequence.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
//~ #define int ll
const int INF = 1e9;
struct ST{
vector<int> min, max, p;
int N;
ST(){
N = 5e5 + 5;
min.resize(N << 2);
max.resize(N << 2);
p.resize(N << 2);
}
ST(int N): N(N) {
min.resize(N << 2);
max.resize(N << 2);
p.resize(N << 2);
}
void push(int x, int lx, int rx){
if(lx == rx) return;
min[x << 1] += p[x], max[x << 1] += p[x], p[x << 1] += p[x];
min[x << 1 | 1] += p[x], max[x << 1 | 1] += p[x], p[x << 1 | 1] += p[x];
p[x] = 0;
}
void add(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
min[x] += v, max[x] += v, p[x] += v;
return;
}
int m = (lx + rx) >> 1;
push(x, lx, rx);
add(l, r, v, lx, m, x << 1), add(l, r, v, m + 1, rx, x << 1 | 1);
min[x] = ::min(min[x << 1], min[x << 1 | 1]);
max[x] = ::max(max[x << 1], max[x << 1 | 1]);
}
void add(int l, int r, int v){
add(l, r, v, 0, N, 1);
}
int Max(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return -INF;
if(lx >= l && rx <= r) return max[x];
int m = (lx + rx) >> 1;
push(x, lx, rx);
return ::max(Max(l, r, lx, m, x << 1), Max(l, r, m + 1, rx, x << 1 | 1));
}
int Max(int l, int r){
return Max(l, r, 0, N, 1);
}
int Min(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return INF;
if(lx >= l && rx <= r) return min[x];
int m = (lx + rx) >> 1;
push(x, lx, rx);
return ::min(Min(l, r, lx, m, x << 1), Min(l, r, m + 1, rx, x << 1 | 1));
}
int Min(int l, int r){
return Min(l, r, 0, N, 1);
}
};
int sequence(int n, vector<int> a) {
a.insert(a.begin(), 0);
ST A, B;
vector<int> p(n);
iota(p.begin(), p.end(), 1);
sort(p.begin(), p.end(), [&](int i, int j){
if(a[i] != a[j]) return a[i] < a[j];
return i < j;
});
for(int i=1;i<=n;i++){
B.add(i, i, i);
A.add(i, i, -i);
}
int res = 0;
for(int i=0,j=0;i<n;){
vector<int> pos;
while(j < n && a[p[i]] == a[p[j]]){
pos.push_back(p[j]);
A.add(p[j], n, 2);
j++;
}
auto check = [&](int m){
for(int k=m - 1;k<(int)pos.size();k++){
int l = k - m + 1, r = k;
if(B.Max(pos[r], n) >= B.Min(0, pos[l] - 1) && A.Max(pos[r], n) >= A.Min(0, pos[l] - 1)) return true;
}
return false;
};
int l = 1, r = j - i;
while(l < r){
int m = (l + r + 1) >> 1;
if(check(m)) l = m;
else r = m - 1;
}
res = max(res, l);
while(i < j){
B.add(p[i], n, -2);
i++;
}
}
return res;
}
/*
7
1 2 3 1 2 1 3
9
1 1 2 3 4 3 2 1 1
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
47308 KB |
Output is correct |
2 |
Correct |
19 ms |
47192 KB |
Output is correct |
3 |
Correct |
20 ms |
47212 KB |
Output is correct |
4 |
Correct |
20 ms |
47168 KB |
Output is correct |
5 |
Correct |
19 ms |
47288 KB |
Output is correct |
6 |
Correct |
20 ms |
47196 KB |
Output is correct |
7 |
Correct |
20 ms |
47188 KB |
Output is correct |
8 |
Correct |
20 ms |
47280 KB |
Output is correct |
9 |
Correct |
19 ms |
47184 KB |
Output is correct |
10 |
Correct |
19 ms |
47212 KB |
Output is correct |
11 |
Correct |
20 ms |
47208 KB |
Output is correct |
12 |
Correct |
19 ms |
47268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
47308 KB |
Output is correct |
2 |
Correct |
19 ms |
47192 KB |
Output is correct |
3 |
Correct |
20 ms |
47212 KB |
Output is correct |
4 |
Correct |
20 ms |
47168 KB |
Output is correct |
5 |
Correct |
19 ms |
47288 KB |
Output is correct |
6 |
Correct |
20 ms |
47196 KB |
Output is correct |
7 |
Correct |
20 ms |
47188 KB |
Output is correct |
8 |
Correct |
20 ms |
47280 KB |
Output is correct |
9 |
Correct |
19 ms |
47184 KB |
Output is correct |
10 |
Correct |
19 ms |
47212 KB |
Output is correct |
11 |
Correct |
20 ms |
47208 KB |
Output is correct |
12 |
Correct |
19 ms |
47268 KB |
Output is correct |
13 |
Correct |
25 ms |
47232 KB |
Output is correct |
14 |
Correct |
24 ms |
47196 KB |
Output is correct |
15 |
Correct |
31 ms |
47304 KB |
Output is correct |
16 |
Correct |
30 ms |
47188 KB |
Output is correct |
17 |
Correct |
31 ms |
47288 KB |
Output is correct |
18 |
Correct |
23 ms |
47316 KB |
Output is correct |
19 |
Correct |
28 ms |
47316 KB |
Output is correct |
20 |
Correct |
28 ms |
47312 KB |
Output is correct |
21 |
Correct |
25 ms |
47248 KB |
Output is correct |
22 |
Correct |
26 ms |
47200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
47308 KB |
Output is correct |
2 |
Correct |
1603 ms |
53168 KB |
Output is correct |
3 |
Correct |
1603 ms |
53164 KB |
Output is correct |
4 |
Execution timed out |
2062 ms |
54068 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
47192 KB |
Output is correct |
2 |
Execution timed out |
2067 ms |
56308 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1436 ms |
53156 KB |
Output is correct |
2 |
Correct |
1522 ms |
53156 KB |
Output is correct |
3 |
Correct |
1550 ms |
53160 KB |
Output is correct |
4 |
Correct |
1480 ms |
53164 KB |
Output is correct |
5 |
Correct |
1581 ms |
53156 KB |
Output is correct |
6 |
Correct |
1663 ms |
53160 KB |
Output is correct |
7 |
Correct |
1556 ms |
53160 KB |
Output is correct |
8 |
Correct |
1589 ms |
53156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
47308 KB |
Output is correct |
2 |
Correct |
19 ms |
47192 KB |
Output is correct |
3 |
Correct |
20 ms |
47212 KB |
Output is correct |
4 |
Correct |
20 ms |
47168 KB |
Output is correct |
5 |
Correct |
19 ms |
47288 KB |
Output is correct |
6 |
Correct |
20 ms |
47196 KB |
Output is correct |
7 |
Correct |
20 ms |
47188 KB |
Output is correct |
8 |
Correct |
20 ms |
47280 KB |
Output is correct |
9 |
Correct |
19 ms |
47184 KB |
Output is correct |
10 |
Correct |
19 ms |
47212 KB |
Output is correct |
11 |
Correct |
20 ms |
47208 KB |
Output is correct |
12 |
Correct |
19 ms |
47268 KB |
Output is correct |
13 |
Correct |
25 ms |
47232 KB |
Output is correct |
14 |
Correct |
24 ms |
47196 KB |
Output is correct |
15 |
Correct |
31 ms |
47304 KB |
Output is correct |
16 |
Correct |
30 ms |
47188 KB |
Output is correct |
17 |
Correct |
31 ms |
47288 KB |
Output is correct |
18 |
Correct |
23 ms |
47316 KB |
Output is correct |
19 |
Correct |
28 ms |
47316 KB |
Output is correct |
20 |
Correct |
28 ms |
47312 KB |
Output is correct |
21 |
Correct |
25 ms |
47248 KB |
Output is correct |
22 |
Correct |
26 ms |
47200 KB |
Output is correct |
23 |
Correct |
253 ms |
48216 KB |
Output is correct |
24 |
Correct |
257 ms |
48144 KB |
Output is correct |
25 |
Correct |
256 ms |
48252 KB |
Output is correct |
26 |
Correct |
590 ms |
48348 KB |
Output is correct |
27 |
Correct |
625 ms |
48228 KB |
Output is correct |
28 |
Correct |
637 ms |
48244 KB |
Output is correct |
29 |
Correct |
819 ms |
48400 KB |
Output is correct |
30 |
Correct |
728 ms |
48348 KB |
Output is correct |
31 |
Correct |
206 ms |
48912 KB |
Output is correct |
32 |
Correct |
202 ms |
48216 KB |
Output is correct |
33 |
Correct |
246 ms |
48232 KB |
Output is correct |
34 |
Correct |
239 ms |
48224 KB |
Output is correct |
35 |
Correct |
231 ms |
48336 KB |
Output is correct |
36 |
Correct |
392 ms |
48344 KB |
Output is correct |
37 |
Correct |
364 ms |
48400 KB |
Output is correct |
38 |
Correct |
297 ms |
48240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
47308 KB |
Output is correct |
2 |
Correct |
19 ms |
47192 KB |
Output is correct |
3 |
Correct |
20 ms |
47212 KB |
Output is correct |
4 |
Correct |
20 ms |
47168 KB |
Output is correct |
5 |
Correct |
19 ms |
47288 KB |
Output is correct |
6 |
Correct |
20 ms |
47196 KB |
Output is correct |
7 |
Correct |
20 ms |
47188 KB |
Output is correct |
8 |
Correct |
20 ms |
47280 KB |
Output is correct |
9 |
Correct |
19 ms |
47184 KB |
Output is correct |
10 |
Correct |
19 ms |
47212 KB |
Output is correct |
11 |
Correct |
20 ms |
47208 KB |
Output is correct |
12 |
Correct |
19 ms |
47268 KB |
Output is correct |
13 |
Correct |
25 ms |
47232 KB |
Output is correct |
14 |
Correct |
24 ms |
47196 KB |
Output is correct |
15 |
Correct |
31 ms |
47304 KB |
Output is correct |
16 |
Correct |
30 ms |
47188 KB |
Output is correct |
17 |
Correct |
31 ms |
47288 KB |
Output is correct |
18 |
Correct |
23 ms |
47316 KB |
Output is correct |
19 |
Correct |
28 ms |
47316 KB |
Output is correct |
20 |
Correct |
28 ms |
47312 KB |
Output is correct |
21 |
Correct |
25 ms |
47248 KB |
Output is correct |
22 |
Correct |
26 ms |
47200 KB |
Output is correct |
23 |
Correct |
1603 ms |
53168 KB |
Output is correct |
24 |
Correct |
1603 ms |
53164 KB |
Output is correct |
25 |
Execution timed out |
2062 ms |
54068 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |