#include <bits/stdc++.h>
using namespace std;
struct Node{
int prefmx, prefmn, sufmx, sufmn, tot, val, totmn, totmx;
};
const int N = 5e5 + 69;
Node seg[4 * N];
Node res;
int n;
Node combine(Node a, Node b){
Node ok;
ok.tot = a.tot + b.tot;
ok.prefmx = max(a.prefmx, b.prefmx + a.totmx);
ok.prefmn = min(a.prefmn, b.prefmn + a.totmn);
ok.sufmx = max(b.sufmx, a.sufmx + b.totmx);
ok.sufmn = min(b.sufmn, a.sufmn + b.totmn);
ok.val = a.val + b.val;
ok.totmx = a.totmx + b.totmx;
ok.totmn = a.totmn + b.totmn;
return ok;
}
void upd(int l, int r, int pos, int qp, int v){
if (l == r){
seg[pos].tot = seg[pos].totmn = seg[pos].totmx = v;
seg[pos].prefmx = max(v, 0);
seg[pos].prefmn = min(v, 0);
seg[pos].sufmx = max(v, 0);
seg[pos].sufmn = min(v, 0);
seg[pos].val = v == 0;
if (v == 0){
seg[pos].sufmx = 1;
seg[pos].sufmn = -1;
seg[pos].prefmn = -1;
seg[pos].prefmx = 1;
seg[pos].totmn = -1;
seg[pos].totmx = 1;
}
return;
}
int mid = (l + r)/2;
if (qp <= mid) upd(l, mid, pos*2, qp, v);
else upd(mid + 1, r, pos*2 + 1, qp, v);
seg[pos] = combine(seg[pos * 2], seg[pos * 2 + 1]);
}
void query(int l, int r, int pos, int ql, int qr){
if (l >= ql && r <= qr) {
res = combine(res, seg[pos]);
return;
} else if (l > qr || r < ql) return;
int mid = (l + r)/2;
query(l, mid, pos*2, ql, qr);
query(mid + 1, r, pos*2 + 1, ql, qr);
}
Node query(int ql, int qr){
res.tot = res.prefmx = res.prefmn = res.sufmx = res.sufmn = res.val = res.totmn = res.totmx = 0;
query(0, n - 1, 1, ql, qr);
return res;
}
void print(Node a){
cout << a.tot << " " << a.val << " " << a.sufmx << " " << a.sufmn << " " << a.prefmx << " " << a.prefmn << "\n";
}
bool good(int a, int b){
Node g1 = query(a, b);
Node g2 = query(0, a - 1);
Node g3 = query(b + 1, n - 1);
// cout << a << " " << b << "\n";
// print(g1);
// print(g2);
// print(g3);
int x = g1.val;
//balance needs to be in range (-x, x)
if (g1.tot + g2.sufmx + g3.prefmx < -x) return false;
if (g1.tot + g2.sufmn + g3.prefmn > x) return false;
return true;
}
int sequence(int m, vector <int> a){
//l1 < a + l2
//l2 < a + l1
//l1 - l2 < a
//l2 -l1 < a, l1 - l2 > -a
//l1 - l2 in range (-a, a)
//l1 is smaller stuff
//l2 is larger stuff
n = m;
vector <int> adj[n + 1];
for (int i = 0; i < n; i++){
upd(0, n - 1, 1, i, 1);
adj[a[i]].push_back(i);
}
int ans = 0;
for (int i = 1; i <= n; i++){
for (auto x : adj[i]){
upd(0, n - 1, 1, x, 0);
}
int r = 0;
for (int l = 0; l < adj[i].size(); l++){
r = max(r, l);
while ((r + 1) < adj[i].size() && good(adj[i][l], adj[i][r + 1])){
r++;
}
// cout << "L " << l << " " << r << "\n";
ans = max(ans, r - l + 1);
}
// for (int l = 0; l < (int)adj[i].size(); l++){
// for (int r = l; r < (int)adj[i].size(); r++){
// if (good(adj[i][l], adj[i][r])) ans = max(ans, r - l + 1);
// }
// }
for (auto x : adj[i]){
upd(0, n - 1, 1, x, -1);
}
}
return ans;
}
// int main(){
// int n; cin >> n;
// vector <int> a(n);
// for (auto &x : a) cin >> x;
// cout << sequence(n, a) << "\n";
// return 0;
// }
Compilation message
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:114:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for (int l = 0; l < adj[i].size(); l++){
| ~~^~~~~~~~~~~~~~~
sequence.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | while ((r + 1) < adj[i].size() && good(adj[i][l], adj[i][r + 1])){
| ~~~~~~~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
2 ms |
444 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
2 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |
22 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
454 ms |
58780 KB |
Output is correct |
3 |
Correct |
460 ms |
58712 KB |
Output is correct |
4 |
Correct |
726 ms |
50884 KB |
Output is correct |
5 |
Correct |
480 ms |
57804 KB |
Output is correct |
6 |
Correct |
447 ms |
57676 KB |
Output is correct |
7 |
Correct |
721 ms |
51148 KB |
Output is correct |
8 |
Correct |
698 ms |
51416 KB |
Output is correct |
9 |
Correct |
653 ms |
50892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
795 ms |
51020 KB |
Output is correct |
3 |
Correct |
715 ms |
50888 KB |
Output is correct |
4 |
Correct |
785 ms |
50880 KB |
Output is correct |
5 |
Correct |
652 ms |
51016 KB |
Output is correct |
6 |
Correct |
820 ms |
50972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
490 ms |
64432 KB |
Output is correct |
2 |
Correct |
470 ms |
64348 KB |
Output is correct |
3 |
Correct |
475 ms |
63836 KB |
Output is correct |
4 |
Correct |
507 ms |
63820 KB |
Output is correct |
5 |
Correct |
477 ms |
60536 KB |
Output is correct |
6 |
Correct |
527 ms |
60460 KB |
Output is correct |
7 |
Correct |
448 ms |
59328 KB |
Output is correct |
8 |
Correct |
451 ms |
58912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
2 ms |
444 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
2 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |
22 |
Correct |
2 ms |
468 KB |
Output is correct |
23 |
Correct |
95 ms |
12596 KB |
Output is correct |
24 |
Correct |
86 ms |
12500 KB |
Output is correct |
25 |
Correct |
83 ms |
12604 KB |
Output is correct |
26 |
Correct |
110 ms |
11684 KB |
Output is correct |
27 |
Correct |
108 ms |
11688 KB |
Output is correct |
28 |
Correct |
113 ms |
11796 KB |
Output is correct |
29 |
Correct |
106 ms |
11348 KB |
Output is correct |
30 |
Correct |
111 ms |
11480 KB |
Output is correct |
31 |
Correct |
86 ms |
11388 KB |
Output is correct |
32 |
Correct |
50 ms |
13524 KB |
Output is correct |
33 |
Correct |
87 ms |
12428 KB |
Output is correct |
34 |
Correct |
85 ms |
12372 KB |
Output is correct |
35 |
Correct |
93 ms |
12368 KB |
Output is correct |
36 |
Correct |
89 ms |
12360 KB |
Output is correct |
37 |
Correct |
88 ms |
12372 KB |
Output is correct |
38 |
Correct |
88 ms |
12360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 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 |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
2 ms |
444 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
2 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |
22 |
Correct |
2 ms |
468 KB |
Output is correct |
23 |
Correct |
454 ms |
58780 KB |
Output is correct |
24 |
Correct |
460 ms |
58712 KB |
Output is correct |
25 |
Correct |
726 ms |
50884 KB |
Output is correct |
26 |
Correct |
480 ms |
57804 KB |
Output is correct |
27 |
Correct |
447 ms |
57676 KB |
Output is correct |
28 |
Correct |
721 ms |
51148 KB |
Output is correct |
29 |
Correct |
698 ms |
51416 KB |
Output is correct |
30 |
Correct |
653 ms |
50892 KB |
Output is correct |
31 |
Correct |
795 ms |
51020 KB |
Output is correct |
32 |
Correct |
715 ms |
50888 KB |
Output is correct |
33 |
Correct |
785 ms |
50880 KB |
Output is correct |
34 |
Correct |
652 ms |
51016 KB |
Output is correct |
35 |
Correct |
820 ms |
50972 KB |
Output is correct |
36 |
Correct |
490 ms |
64432 KB |
Output is correct |
37 |
Correct |
470 ms |
64348 KB |
Output is correct |
38 |
Correct |
475 ms |
63836 KB |
Output is correct |
39 |
Correct |
507 ms |
63820 KB |
Output is correct |
40 |
Correct |
477 ms |
60536 KB |
Output is correct |
41 |
Correct |
527 ms |
60460 KB |
Output is correct |
42 |
Correct |
448 ms |
59328 KB |
Output is correct |
43 |
Correct |
451 ms |
58912 KB |
Output is correct |
44 |
Correct |
95 ms |
12596 KB |
Output is correct |
45 |
Correct |
86 ms |
12500 KB |
Output is correct |
46 |
Correct |
83 ms |
12604 KB |
Output is correct |
47 |
Correct |
110 ms |
11684 KB |
Output is correct |
48 |
Correct |
108 ms |
11688 KB |
Output is correct |
49 |
Correct |
113 ms |
11796 KB |
Output is correct |
50 |
Correct |
106 ms |
11348 KB |
Output is correct |
51 |
Correct |
111 ms |
11480 KB |
Output is correct |
52 |
Correct |
86 ms |
11388 KB |
Output is correct |
53 |
Correct |
50 ms |
13524 KB |
Output is correct |
54 |
Correct |
87 ms |
12428 KB |
Output is correct |
55 |
Correct |
85 ms |
12372 KB |
Output is correct |
56 |
Correct |
93 ms |
12368 KB |
Output is correct |
57 |
Correct |
89 ms |
12360 KB |
Output is correct |
58 |
Correct |
88 ms |
12372 KB |
Output is correct |
59 |
Correct |
88 ms |
12360 KB |
Output is correct |
60 |
Correct |
759 ms |
58716 KB |
Output is correct |
61 |
Correct |
757 ms |
58812 KB |
Output is correct |
62 |
Correct |
728 ms |
58712 KB |
Output is correct |
63 |
Correct |
845 ms |
51996 KB |
Output is correct |
64 |
Correct |
860 ms |
52008 KB |
Output is correct |
65 |
Correct |
854 ms |
51972 KB |
Output is correct |
66 |
Correct |
788 ms |
50920 KB |
Output is correct |
67 |
Correct |
787 ms |
51140 KB |
Output is correct |
68 |
Correct |
520 ms |
50752 KB |
Output is correct |
69 |
Correct |
335 ms |
64516 KB |
Output is correct |
70 |
Correct |
772 ms |
57712 KB |
Output is correct |
71 |
Correct |
756 ms |
57540 KB |
Output is correct |
72 |
Correct |
736 ms |
57088 KB |
Output is correct |
73 |
Correct |
751 ms |
57452 KB |
Output is correct |
74 |
Correct |
756 ms |
57044 KB |
Output is correct |
75 |
Correct |
746 ms |
57448 KB |
Output is correct |