#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
struct node{
int s, e, m;
int mx, mn, lazy;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
if(s != e)l = new node(s, m), r = new node(m+1, e);
lazy = 0;
mn = s + 1, mx = e + 1;
}
void prop(){
if(!lazy)return;
mx += lazy, mn += lazy;
if(s != e)l->lazy += lazy, r->lazy += lazy;
lazy = 0;
}
void upd(int a, int b, int c){
if(a == s && b == e)lazy += c;
else{
if(b <= m)l->upd(a, b, c);
else if(a > m)r->upd(a, b, c);
else l->upd(a, m, c), r->upd(m+1, b, c);
l->prop(), r->prop();
mn= min(l->mn, r->mn);
mx= max(l->mx, r->mx);
}
}
pi qry(int a, int b){
prop();
if(a == s && b == e)return {mn, mx};
if(b <= m)return l->qry(a, b);
else if(a > m)return r->qry(a, b);
else{
pi lft = l->qry(a, m), rgt = r->qry(m+1 ,b);
return {min(lft.fi, rgt.fi), max(lft.se, rgt.se)};
}
}
int qm(int a, int b){
prop();
if(a == s && b == e)return mx;
if(b <= m)return l->qm(a, b);
if(a > m)return r->qm(a, b);
return max(l->qm(a, m), r->qm(m+1, b));
}
int qmm(int a, int b){
prop();
if(a == s && b == e)return mn;
if(b <= m)return l->qmm(a, b);
if(a > m)return r->qmm(a, b);
return min(l->qmm(a, m), r->qmm(m+1, b));
}
}*lft;
struct node2{
int s, e, m;
int mx, mn, lazy;
node2 *l, *r;
node2(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
if(s != e)l = new node2(s, m), r = new node2(m+1, e);
lazy = 0, mx = (n - s), mn = (n - e);
}
void prop(){
if(!lazy)return;
mx += lazy, mn += lazy;
if(s != e)l->lazy += lazy, r->lazy += lazy;
lazy = 0;
}
void upd(int a, int b, int c){
if(a == s && b == e)lazy += c;
else{
if(b <= m)l->upd(a, b, c);
else if(a > m)r->upd(a, b, c);
else l->upd(a, m, c), r->upd(m+1, b, c);
l->prop(), r->prop();
mn= min(l->mn, r->mn);
mx= max(l->mx, r->mx);
}
}
int qm(int a, int b){
prop();
if(a == s && b == e)return mx;
if(b <= m)return l->qm(a, b);
if(a > m)return r->qm(a, b);
return max(l->qm(a, m), r->qm(m+1, b));
}
int qmm(int a, int b){
prop();
if(a == s && b == e)return mn;
if(b <= m)return l->qmm(a, b);
if(a > m)return r->qmm(a, b);
return min(l->qmm(a, m), r->qmm(m+1, b));
}
}*rgt;
vector <int> occ[500005];
int B[10][500001];
int sequence(int N, vector <int> A){
n = N;
for(int i=0;i<N;i++)occ[A[i]].push_back(i);
lft = new node(0, N - 1);
rgt = new node2(0, N - 1);
int ans = 1;
for(int i=1;i<=N;i++){
int in = 0;
for(int j = 0; j < (int)occ[i].size(); j++){
int r = occ[i][j];
int tmp2 = lft->qm(r, N - 1), ref2 = lft->qm(r, r), tmp = rgt->qm(0, r);
int ref = rgt->qm(r, r);
tmp -= ref;
int tmp5 = (r == 0 ? 0 : ref2 - 1);
tmp2 -= ref2;
B[0][j] = tmp, B[1][j] = ref, B[2][j] = tmp2, B[3][j] = ref2, B[8][j] = tmp5;
}
for(auto j : occ[i]){
lft->upd(j, N - 1, -2);
rgt->upd(0, j, -2);
}
for(int j = 0; j < (int)occ[i].size(); j++){
int r = occ[i][j];
int tmp4 = lft->qmm(r, N - 1), ref4 = lft->qmm(r, r);
tmp4 -= ref4;
int tmp3 = rgt->qmm(0, r);
int ref3 = rgt->qmm(r, r);
tmp3 -= ref3;
int tmp6 = (r == 0 ? 0 : ref4 + 1);
B[4][j] = tmp3, B[5][j] = ref3, B[6][j] = tmp4, B[7][j] = ref4, B[9][j] = tmp6;
int tmp2 = B[2][j], ref2 = B[3][j];
while(in < j){
int tmp = B[0][in];
tmp3 = B[4][in], ref3 = B[5][in];
tmp += tmp2;
tmp3 += tmp4;
int val = ref2 - B[8][in];
int val2 = ref4 - B[9][in];
long long mn = val + tmp, mx = val2 + tmp3;
if(mn * mx > 0)in++;
else break;
}
//cout << i << ' ' << j << ' ' << in << '\n';
ans = max(ans, j - in + 1);
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
6 ms |
12116 KB |
Output is correct |
3 |
Correct |
6 ms |
12116 KB |
Output is correct |
4 |
Correct |
7 ms |
12116 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12116 KB |
Output is correct |
7 |
Correct |
7 ms |
12116 KB |
Output is correct |
8 |
Correct |
6 ms |
12116 KB |
Output is correct |
9 |
Correct |
6 ms |
12068 KB |
Output is correct |
10 |
Correct |
7 ms |
12084 KB |
Output is correct |
11 |
Correct |
7 ms |
12140 KB |
Output is correct |
12 |
Correct |
7 ms |
12116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
6 ms |
12116 KB |
Output is correct |
3 |
Correct |
6 ms |
12116 KB |
Output is correct |
4 |
Correct |
7 ms |
12116 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12116 KB |
Output is correct |
7 |
Correct |
7 ms |
12116 KB |
Output is correct |
8 |
Correct |
6 ms |
12116 KB |
Output is correct |
9 |
Correct |
6 ms |
12068 KB |
Output is correct |
10 |
Correct |
7 ms |
12084 KB |
Output is correct |
11 |
Correct |
7 ms |
12140 KB |
Output is correct |
12 |
Correct |
7 ms |
12116 KB |
Output is correct |
13 |
Correct |
9 ms |
12500 KB |
Output is correct |
14 |
Correct |
10 ms |
12524 KB |
Output is correct |
15 |
Correct |
9 ms |
12404 KB |
Output is correct |
16 |
Correct |
10 ms |
12500 KB |
Output is correct |
17 |
Correct |
9 ms |
12500 KB |
Output is correct |
18 |
Correct |
9 ms |
12500 KB |
Output is correct |
19 |
Correct |
10 ms |
12452 KB |
Output is correct |
20 |
Correct |
9 ms |
12564 KB |
Output is correct |
21 |
Correct |
10 ms |
12508 KB |
Output is correct |
22 |
Correct |
10 ms |
12548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
776 ms |
119864 KB |
Output is correct |
3 |
Correct |
821 ms |
119924 KB |
Output is correct |
4 |
Correct |
664 ms |
115796 KB |
Output is correct |
5 |
Correct |
816 ms |
118948 KB |
Output is correct |
6 |
Correct |
755 ms |
118988 KB |
Output is correct |
7 |
Correct |
658 ms |
112700 KB |
Output is correct |
8 |
Correct |
654 ms |
112716 KB |
Output is correct |
9 |
Correct |
666 ms |
119084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
803 ms |
122708 KB |
Output is correct |
3 |
Correct |
776 ms |
118624 KB |
Output is correct |
4 |
Correct |
758 ms |
118432 KB |
Output is correct |
5 |
Correct |
752 ms |
122852 KB |
Output is correct |
6 |
Correct |
699 ms |
121756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1447 ms |
125624 KB |
Output is correct |
2 |
Correct |
1424 ms |
125744 KB |
Output is correct |
3 |
Correct |
1429 ms |
125040 KB |
Output is correct |
4 |
Correct |
1492 ms |
125136 KB |
Output is correct |
5 |
Correct |
1113 ms |
121804 KB |
Output is correct |
6 |
Correct |
1128 ms |
121708 KB |
Output is correct |
7 |
Correct |
819 ms |
120484 KB |
Output is correct |
8 |
Correct |
843 ms |
120196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
6 ms |
12116 KB |
Output is correct |
3 |
Correct |
6 ms |
12116 KB |
Output is correct |
4 |
Correct |
7 ms |
12116 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12116 KB |
Output is correct |
7 |
Correct |
7 ms |
12116 KB |
Output is correct |
8 |
Correct |
6 ms |
12116 KB |
Output is correct |
9 |
Correct |
6 ms |
12068 KB |
Output is correct |
10 |
Correct |
7 ms |
12084 KB |
Output is correct |
11 |
Correct |
7 ms |
12140 KB |
Output is correct |
12 |
Correct |
7 ms |
12116 KB |
Output is correct |
13 |
Correct |
9 ms |
12500 KB |
Output is correct |
14 |
Correct |
10 ms |
12524 KB |
Output is correct |
15 |
Correct |
9 ms |
12404 KB |
Output is correct |
16 |
Correct |
10 ms |
12500 KB |
Output is correct |
17 |
Correct |
9 ms |
12500 KB |
Output is correct |
18 |
Correct |
9 ms |
12500 KB |
Output is correct |
19 |
Correct |
10 ms |
12452 KB |
Output is correct |
20 |
Correct |
9 ms |
12564 KB |
Output is correct |
21 |
Correct |
10 ms |
12508 KB |
Output is correct |
22 |
Correct |
10 ms |
12548 KB |
Output is correct |
23 |
Correct |
238 ms |
29260 KB |
Output is correct |
24 |
Correct |
227 ms |
29268 KB |
Output is correct |
25 |
Correct |
215 ms |
29316 KB |
Output is correct |
26 |
Correct |
218 ms |
28244 KB |
Output is correct |
27 |
Correct |
215 ms |
28368 KB |
Output is correct |
28 |
Correct |
205 ms |
28316 KB |
Output is correct |
29 |
Correct |
139 ms |
28740 KB |
Output is correct |
30 |
Correct |
126 ms |
28640 KB |
Output is correct |
31 |
Correct |
101 ms |
31156 KB |
Output is correct |
32 |
Correct |
105 ms |
30300 KB |
Output is correct |
33 |
Correct |
214 ms |
29588 KB |
Output is correct |
34 |
Correct |
215 ms |
29448 KB |
Output is correct |
35 |
Correct |
208 ms |
29504 KB |
Output is correct |
36 |
Correct |
229 ms |
29512 KB |
Output is correct |
37 |
Correct |
219 ms |
29436 KB |
Output is correct |
38 |
Correct |
225 ms |
29692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
6 ms |
12116 KB |
Output is correct |
3 |
Correct |
6 ms |
12116 KB |
Output is correct |
4 |
Correct |
7 ms |
12116 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12116 KB |
Output is correct |
7 |
Correct |
7 ms |
12116 KB |
Output is correct |
8 |
Correct |
6 ms |
12116 KB |
Output is correct |
9 |
Correct |
6 ms |
12068 KB |
Output is correct |
10 |
Correct |
7 ms |
12084 KB |
Output is correct |
11 |
Correct |
7 ms |
12140 KB |
Output is correct |
12 |
Correct |
7 ms |
12116 KB |
Output is correct |
13 |
Correct |
9 ms |
12500 KB |
Output is correct |
14 |
Correct |
10 ms |
12524 KB |
Output is correct |
15 |
Correct |
9 ms |
12404 KB |
Output is correct |
16 |
Correct |
10 ms |
12500 KB |
Output is correct |
17 |
Correct |
9 ms |
12500 KB |
Output is correct |
18 |
Correct |
9 ms |
12500 KB |
Output is correct |
19 |
Correct |
10 ms |
12452 KB |
Output is correct |
20 |
Correct |
9 ms |
12564 KB |
Output is correct |
21 |
Correct |
10 ms |
12508 KB |
Output is correct |
22 |
Correct |
10 ms |
12548 KB |
Output is correct |
23 |
Correct |
776 ms |
119864 KB |
Output is correct |
24 |
Correct |
821 ms |
119924 KB |
Output is correct |
25 |
Correct |
664 ms |
115796 KB |
Output is correct |
26 |
Correct |
816 ms |
118948 KB |
Output is correct |
27 |
Correct |
755 ms |
118988 KB |
Output is correct |
28 |
Correct |
658 ms |
112700 KB |
Output is correct |
29 |
Correct |
654 ms |
112716 KB |
Output is correct |
30 |
Correct |
666 ms |
119084 KB |
Output is correct |
31 |
Correct |
803 ms |
122708 KB |
Output is correct |
32 |
Correct |
776 ms |
118624 KB |
Output is correct |
33 |
Correct |
758 ms |
118432 KB |
Output is correct |
34 |
Correct |
752 ms |
122852 KB |
Output is correct |
35 |
Correct |
699 ms |
121756 KB |
Output is correct |
36 |
Correct |
1447 ms |
125624 KB |
Output is correct |
37 |
Correct |
1424 ms |
125744 KB |
Output is correct |
38 |
Correct |
1429 ms |
125040 KB |
Output is correct |
39 |
Correct |
1492 ms |
125136 KB |
Output is correct |
40 |
Correct |
1113 ms |
121804 KB |
Output is correct |
41 |
Correct |
1128 ms |
121708 KB |
Output is correct |
42 |
Correct |
819 ms |
120484 KB |
Output is correct |
43 |
Correct |
843 ms |
120196 KB |
Output is correct |
44 |
Correct |
238 ms |
29260 KB |
Output is correct |
45 |
Correct |
227 ms |
29268 KB |
Output is correct |
46 |
Correct |
215 ms |
29316 KB |
Output is correct |
47 |
Correct |
218 ms |
28244 KB |
Output is correct |
48 |
Correct |
215 ms |
28368 KB |
Output is correct |
49 |
Correct |
205 ms |
28316 KB |
Output is correct |
50 |
Correct |
139 ms |
28740 KB |
Output is correct |
51 |
Correct |
126 ms |
28640 KB |
Output is correct |
52 |
Correct |
101 ms |
31156 KB |
Output is correct |
53 |
Correct |
105 ms |
30300 KB |
Output is correct |
54 |
Correct |
214 ms |
29588 KB |
Output is correct |
55 |
Correct |
215 ms |
29448 KB |
Output is correct |
56 |
Correct |
208 ms |
29504 KB |
Output is correct |
57 |
Correct |
229 ms |
29512 KB |
Output is correct |
58 |
Correct |
219 ms |
29436 KB |
Output is correct |
59 |
Correct |
225 ms |
29692 KB |
Output is correct |
60 |
Correct |
1985 ms |
119988 KB |
Output is correct |
61 |
Correct |
1903 ms |
119856 KB |
Output is correct |
62 |
Correct |
1927 ms |
119956 KB |
Output is correct |
63 |
Correct |
1910 ms |
112824 KB |
Output is correct |
64 |
Correct |
1921 ms |
112828 KB |
Output is correct |
65 |
Correct |
1954 ms |
112944 KB |
Output is correct |
66 |
Correct |
819 ms |
116024 KB |
Output is correct |
67 |
Correct |
836 ms |
115928 KB |
Output is correct |
68 |
Correct |
684 ms |
131372 KB |
Output is correct |
69 |
Correct |
683 ms |
125640 KB |
Output is correct |
70 |
Correct |
1796 ms |
121236 KB |
Output is correct |
71 |
Correct |
1812 ms |
121344 KB |
Output is correct |
72 |
Correct |
1720 ms |
121652 KB |
Output is correct |
73 |
Correct |
1822 ms |
121504 KB |
Output is correct |
74 |
Correct |
1769 ms |
121912 KB |
Output is correct |
75 |
Correct |
1786 ms |
121316 KB |
Output is correct |