#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;
const int N = 5e5 + 5;
int A_[N], B_[N];
struct ST{
int min[N << 2], max[N << 2], p[N << 2];
ST(){
memset(min, 0, sizeof min);
memset(max, 0, sizeof max);
memset(p, 0, sizeof p);
}
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;){
while(j < n && a[p[i]] == a[p[j]]){
A.add(p[j], n, 2);
j++;
}
for(int k=0;i + k<j;k++){
A_[k] = A.Min(0, p[i + k] - 1);
B_[k] = B.Min(0, p[i + k] - 1);
int MxA = A.Max(p[i + k], n), MxB = B.Max(p[i + k], n);
int l = 0, r = k;
while(l < r){
int m = (l + r) >> 1;
if(A_[m] <= MxA && B_[m] <= MxB) r = m;
else l = m + 1;
}
res = max(res, k - l + 1);
}
while(i < j){
B.add(p[i], n, -2);
i++;
}
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47268 KB |
Output is correct |
2 |
Correct |
25 ms |
47188 KB |
Output is correct |
3 |
Correct |
26 ms |
47204 KB |
Output is correct |
4 |
Correct |
25 ms |
47184 KB |
Output is correct |
5 |
Correct |
25 ms |
47188 KB |
Output is correct |
6 |
Correct |
25 ms |
47188 KB |
Output is correct |
7 |
Correct |
23 ms |
47268 KB |
Output is correct |
8 |
Correct |
22 ms |
47184 KB |
Output is correct |
9 |
Correct |
24 ms |
47188 KB |
Output is correct |
10 |
Correct |
25 ms |
47180 KB |
Output is correct |
11 |
Correct |
26 ms |
47204 KB |
Output is correct |
12 |
Correct |
25 ms |
47248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47268 KB |
Output is correct |
2 |
Correct |
25 ms |
47188 KB |
Output is correct |
3 |
Correct |
26 ms |
47204 KB |
Output is correct |
4 |
Correct |
25 ms |
47184 KB |
Output is correct |
5 |
Correct |
25 ms |
47188 KB |
Output is correct |
6 |
Correct |
25 ms |
47188 KB |
Output is correct |
7 |
Correct |
23 ms |
47268 KB |
Output is correct |
8 |
Correct |
22 ms |
47184 KB |
Output is correct |
9 |
Correct |
24 ms |
47188 KB |
Output is correct |
10 |
Correct |
25 ms |
47180 KB |
Output is correct |
11 |
Correct |
26 ms |
47204 KB |
Output is correct |
12 |
Correct |
25 ms |
47248 KB |
Output is correct |
13 |
Correct |
33 ms |
47212 KB |
Output is correct |
14 |
Correct |
30 ms |
47300 KB |
Output is correct |
15 |
Correct |
31 ms |
47232 KB |
Output is correct |
16 |
Correct |
28 ms |
47188 KB |
Output is correct |
17 |
Correct |
30 ms |
47268 KB |
Output is correct |
18 |
Correct |
29 ms |
47224 KB |
Output is correct |
19 |
Correct |
30 ms |
47284 KB |
Output is correct |
20 |
Correct |
31 ms |
47276 KB |
Output is correct |
21 |
Correct |
30 ms |
47204 KB |
Output is correct |
22 |
Correct |
32 ms |
47188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47268 KB |
Output is correct |
2 |
Correct |
1283 ms |
53088 KB |
Output is correct |
3 |
Correct |
1384 ms |
53152 KB |
Output is correct |
4 |
Correct |
1282 ms |
53944 KB |
Output is correct |
5 |
Correct |
1325 ms |
53148 KB |
Output is correct |
6 |
Correct |
1300 ms |
53140 KB |
Output is correct |
7 |
Correct |
1260 ms |
53160 KB |
Output is correct |
8 |
Correct |
1277 ms |
53148 KB |
Output is correct |
9 |
Correct |
1240 ms |
54560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
47188 KB |
Output is correct |
2 |
Correct |
1333 ms |
55228 KB |
Output is correct |
3 |
Correct |
1335 ms |
54456 KB |
Output is correct |
4 |
Correct |
1394 ms |
54572 KB |
Output is correct |
5 |
Correct |
1307 ms |
55464 KB |
Output is correct |
6 |
Correct |
1279 ms |
55068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1512 ms |
53148 KB |
Output is correct |
2 |
Correct |
1499 ms |
53148 KB |
Output is correct |
3 |
Correct |
1506 ms |
53068 KB |
Output is correct |
4 |
Correct |
1529 ms |
53156 KB |
Output is correct |
5 |
Correct |
1418 ms |
53152 KB |
Output is correct |
6 |
Correct |
1397 ms |
53068 KB |
Output is correct |
7 |
Correct |
1324 ms |
53080 KB |
Output is correct |
8 |
Correct |
1384 ms |
53148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47268 KB |
Output is correct |
2 |
Correct |
25 ms |
47188 KB |
Output is correct |
3 |
Correct |
26 ms |
47204 KB |
Output is correct |
4 |
Correct |
25 ms |
47184 KB |
Output is correct |
5 |
Correct |
25 ms |
47188 KB |
Output is correct |
6 |
Correct |
25 ms |
47188 KB |
Output is correct |
7 |
Correct |
23 ms |
47268 KB |
Output is correct |
8 |
Correct |
22 ms |
47184 KB |
Output is correct |
9 |
Correct |
24 ms |
47188 KB |
Output is correct |
10 |
Correct |
25 ms |
47180 KB |
Output is correct |
11 |
Correct |
26 ms |
47204 KB |
Output is correct |
12 |
Correct |
25 ms |
47248 KB |
Output is correct |
13 |
Correct |
33 ms |
47212 KB |
Output is correct |
14 |
Correct |
30 ms |
47300 KB |
Output is correct |
15 |
Correct |
31 ms |
47232 KB |
Output is correct |
16 |
Correct |
28 ms |
47188 KB |
Output is correct |
17 |
Correct |
30 ms |
47268 KB |
Output is correct |
18 |
Correct |
29 ms |
47224 KB |
Output is correct |
19 |
Correct |
30 ms |
47284 KB |
Output is correct |
20 |
Correct |
31 ms |
47276 KB |
Output is correct |
21 |
Correct |
30 ms |
47204 KB |
Output is correct |
22 |
Correct |
32 ms |
47188 KB |
Output is correct |
23 |
Correct |
245 ms |
48212 KB |
Output is correct |
24 |
Correct |
248 ms |
48216 KB |
Output is correct |
25 |
Correct |
238 ms |
48192 KB |
Output is correct |
26 |
Correct |
235 ms |
48220 KB |
Output is correct |
27 |
Correct |
233 ms |
48212 KB |
Output is correct |
28 |
Correct |
234 ms |
48216 KB |
Output is correct |
29 |
Correct |
219 ms |
48340 KB |
Output is correct |
30 |
Correct |
220 ms |
48220 KB |
Output is correct |
31 |
Correct |
208 ms |
48788 KB |
Output is correct |
32 |
Correct |
203 ms |
48212 KB |
Output is correct |
33 |
Correct |
233 ms |
48232 KB |
Output is correct |
34 |
Correct |
224 ms |
48220 KB |
Output is correct |
35 |
Correct |
221 ms |
48272 KB |
Output is correct |
36 |
Correct |
232 ms |
48308 KB |
Output is correct |
37 |
Correct |
229 ms |
48200 KB |
Output is correct |
38 |
Correct |
233 ms |
48280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47268 KB |
Output is correct |
2 |
Correct |
25 ms |
47188 KB |
Output is correct |
3 |
Correct |
26 ms |
47204 KB |
Output is correct |
4 |
Correct |
25 ms |
47184 KB |
Output is correct |
5 |
Correct |
25 ms |
47188 KB |
Output is correct |
6 |
Correct |
25 ms |
47188 KB |
Output is correct |
7 |
Correct |
23 ms |
47268 KB |
Output is correct |
8 |
Correct |
22 ms |
47184 KB |
Output is correct |
9 |
Correct |
24 ms |
47188 KB |
Output is correct |
10 |
Correct |
25 ms |
47180 KB |
Output is correct |
11 |
Correct |
26 ms |
47204 KB |
Output is correct |
12 |
Correct |
25 ms |
47248 KB |
Output is correct |
13 |
Correct |
33 ms |
47212 KB |
Output is correct |
14 |
Correct |
30 ms |
47300 KB |
Output is correct |
15 |
Correct |
31 ms |
47232 KB |
Output is correct |
16 |
Correct |
28 ms |
47188 KB |
Output is correct |
17 |
Correct |
30 ms |
47268 KB |
Output is correct |
18 |
Correct |
29 ms |
47224 KB |
Output is correct |
19 |
Correct |
30 ms |
47284 KB |
Output is correct |
20 |
Correct |
31 ms |
47276 KB |
Output is correct |
21 |
Correct |
30 ms |
47204 KB |
Output is correct |
22 |
Correct |
32 ms |
47188 KB |
Output is correct |
23 |
Correct |
1283 ms |
53088 KB |
Output is correct |
24 |
Correct |
1384 ms |
53152 KB |
Output is correct |
25 |
Correct |
1282 ms |
53944 KB |
Output is correct |
26 |
Correct |
1325 ms |
53148 KB |
Output is correct |
27 |
Correct |
1300 ms |
53140 KB |
Output is correct |
28 |
Correct |
1260 ms |
53160 KB |
Output is correct |
29 |
Correct |
1277 ms |
53148 KB |
Output is correct |
30 |
Correct |
1240 ms |
54560 KB |
Output is correct |
31 |
Correct |
1333 ms |
55228 KB |
Output is correct |
32 |
Correct |
1335 ms |
54456 KB |
Output is correct |
33 |
Correct |
1394 ms |
54572 KB |
Output is correct |
34 |
Correct |
1307 ms |
55464 KB |
Output is correct |
35 |
Correct |
1279 ms |
55068 KB |
Output is correct |
36 |
Correct |
1512 ms |
53148 KB |
Output is correct |
37 |
Correct |
1499 ms |
53148 KB |
Output is correct |
38 |
Correct |
1506 ms |
53068 KB |
Output is correct |
39 |
Correct |
1529 ms |
53156 KB |
Output is correct |
40 |
Correct |
1418 ms |
53152 KB |
Output is correct |
41 |
Correct |
1397 ms |
53068 KB |
Output is correct |
42 |
Correct |
1324 ms |
53080 KB |
Output is correct |
43 |
Correct |
1384 ms |
53148 KB |
Output is correct |
44 |
Correct |
245 ms |
48212 KB |
Output is correct |
45 |
Correct |
248 ms |
48216 KB |
Output is correct |
46 |
Correct |
238 ms |
48192 KB |
Output is correct |
47 |
Correct |
235 ms |
48220 KB |
Output is correct |
48 |
Correct |
233 ms |
48212 KB |
Output is correct |
49 |
Correct |
234 ms |
48216 KB |
Output is correct |
50 |
Correct |
219 ms |
48340 KB |
Output is correct |
51 |
Correct |
220 ms |
48220 KB |
Output is correct |
52 |
Correct |
208 ms |
48788 KB |
Output is correct |
53 |
Correct |
203 ms |
48212 KB |
Output is correct |
54 |
Correct |
233 ms |
48232 KB |
Output is correct |
55 |
Correct |
224 ms |
48220 KB |
Output is correct |
56 |
Correct |
221 ms |
48272 KB |
Output is correct |
57 |
Correct |
232 ms |
48308 KB |
Output is correct |
58 |
Correct |
229 ms |
48200 KB |
Output is correct |
59 |
Correct |
233 ms |
48280 KB |
Output is correct |
60 |
Correct |
1699 ms |
53148 KB |
Output is correct |
61 |
Correct |
1730 ms |
53068 KB |
Output is correct |
62 |
Correct |
1651 ms |
53196 KB |
Output is correct |
63 |
Correct |
1598 ms |
53176 KB |
Output is correct |
64 |
Correct |
1662 ms |
53144 KB |
Output is correct |
65 |
Correct |
1558 ms |
53076 KB |
Output is correct |
66 |
Correct |
1333 ms |
53868 KB |
Output is correct |
67 |
Correct |
1273 ms |
53952 KB |
Output is correct |
68 |
Correct |
1318 ms |
57004 KB |
Output is correct |
69 |
Correct |
1283 ms |
53152 KB |
Output is correct |
70 |
Correct |
1615 ms |
53532 KB |
Output is correct |
71 |
Correct |
1575 ms |
53700 KB |
Output is correct |
72 |
Correct |
1617 ms |
53780 KB |
Output is correct |
73 |
Correct |
1565 ms |
53660 KB |
Output is correct |
74 |
Correct |
1654 ms |
53964 KB |
Output is correct |
75 |
Correct |
1670 ms |
53608 KB |
Output is correct |