#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MAX = 5e5 + 5;
int A[MAX];
vector <int> pos[MAX], max_pref[MAX], min_pref[MAX], max_suff[MAX], min_suff[MAX];
struct node {
int ma, mi, lazy;
node(int ma = 0, int mi = 0) : ma(ma), mi(mi), lazy(0) {}
} it[MAX << 2];
node merge(const node &a, const node &b) {
return node(max(a.ma, b.ma), min(a.mi, b.mi));
}
void build(int idx, int l, int r) {
if(l == r) it[idx] = node(l, r);
else {
int mid = l + r >> 1;
build(idx << 1, l, mid);
build(idx << 1 | 1, mid + 1, r);
it[idx] = merge(it[idx << 1], it[idx << 1 | 1]);
}
}
void push(int idx) {
if(!it[idx].lazy) return;
it[idx << 1].ma += it[idx].lazy;
it[idx << 1].mi += it[idx].lazy;
it[idx << 1 | 1].ma += it[idx].lazy;
it[idx << 1 | 1].mi += it[idx].lazy;
it[idx << 1].lazy += it[idx].lazy;
it[idx << 1 | 1].lazy += it[idx].lazy;
it[idx].lazy = 0;
}
void update(int idx, int l, int r, int u, int v, int val) {
if(l > v || r < u) return;
if(l >= u && r <= v) {
it[idx].ma += val;
it[idx].mi += val;
it[idx].lazy += val;
return;
}
push(idx);
int mid = l + r >> 1;
update(idx << 1, l, mid, u, v, val);
update(idx << 1 | 1, mid + 1, r, u, v, val);
it[idx] = merge(it[idx << 1], it[idx << 1 | 1]);
}
node get(int idx, int l, int r, int u, int v) {
if(l > v || r < u) return node(-1e9, 1e9);
if(l >= u && r <= v) return it[idx];
push(idx);
int mid = l + r >> 1;
return merge(get(idx << 1, l, mid, u, v), get(idx << 1 | 1, mid + 1, r, u, v));
}
int sequence(int n, vector <int> a) {
for (int i = 0; i < n; ++i) A[i + 1] = a[i];
for (int i = 1; i <= n; ++i) pos[A[i]].push_back(i);
// for (int i = 1; i <= n; ++i) cout << A[i] << " \n"[i == n];
build(1, 0, n);
for (int i = 1; i <= n; ++i) {
for (auto &j : pos[i]) {
min_pref[i].push_back(get(1, 0, n, 0, j - 1).mi);
max_suff[i].push_back(get(1, 0, n, j, n).ma);
}
for (auto &j : pos[i]) update(1, 0, n, j, n, -2);
for (auto &j : pos[i]) {
min_suff[i].push_back(get(1, 0, n, j, n).mi);
max_pref[i].push_back(get(1, 0, n, 0, j - 1).ma);
}
}
auto check = [&] (int res) -> bool {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j + res - 1 < (int) pos[i].size(); ++j) {
if(max_pref[i][j] >= min_suff[i][j + res - 1] && max_suff[i][j + res - 1] >= min_pref[i][j]) {
return true;
}
}
}
return false;
};
int l = -1, r = n + 1;
// for (auto x : max_pref[1]) cout << x << " "; cout << '\n';
// for (auto x : min_pref[1]) cout << x << " "; cout << '\n';
// for (auto x : max_suff[1]) cout << x << " "; cout << '\n';
// for (auto x : min_suff[1]) cout << x << " "; cout << '\n';
// cout << check(3) << '\n';
while(r - l > 1) {
int mid = l + r >> 1;
// cout << mid << endl;
if(check(mid)) l = mid;
else r = mid;
}
return l;
}
#ifdef local
signed main() {
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
int n; cin >> n; vector <int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
cout << sequence(n, a);
}
#endif // local
Compilation message
sequence.cpp: In function 'void build(int, int, int)':
sequence.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | int mid = l + r >> 1;
| ~~^~~
sequence.cpp: In function 'void update(int, int, int, int, int, int)':
sequence.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = l + r >> 1;
| ~~^~~
sequence.cpp: In function 'node get(int, int, int, int, int)':
sequence.cpp:68:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int mid = l + r >> 1;
| ~~^~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:109:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | int mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
82520 KB |
Output is correct |
2 |
Correct |
17 ms |
82524 KB |
Output is correct |
3 |
Correct |
17 ms |
82524 KB |
Output is correct |
4 |
Correct |
18 ms |
82968 KB |
Output is correct |
5 |
Correct |
18 ms |
82700 KB |
Output is correct |
6 |
Correct |
18 ms |
82524 KB |
Output is correct |
7 |
Correct |
17 ms |
82524 KB |
Output is correct |
8 |
Correct |
18 ms |
82524 KB |
Output is correct |
9 |
Correct |
19 ms |
82676 KB |
Output is correct |
10 |
Correct |
18 ms |
82656 KB |
Output is correct |
11 |
Correct |
18 ms |
82520 KB |
Output is correct |
12 |
Correct |
17 ms |
82520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
82520 KB |
Output is correct |
2 |
Correct |
17 ms |
82524 KB |
Output is correct |
3 |
Correct |
17 ms |
82524 KB |
Output is correct |
4 |
Correct |
18 ms |
82968 KB |
Output is correct |
5 |
Correct |
18 ms |
82700 KB |
Output is correct |
6 |
Correct |
18 ms |
82524 KB |
Output is correct |
7 |
Correct |
17 ms |
82524 KB |
Output is correct |
8 |
Correct |
18 ms |
82524 KB |
Output is correct |
9 |
Correct |
19 ms |
82676 KB |
Output is correct |
10 |
Correct |
18 ms |
82656 KB |
Output is correct |
11 |
Correct |
18 ms |
82520 KB |
Output is correct |
12 |
Correct |
17 ms |
82520 KB |
Output is correct |
13 |
Correct |
20 ms |
82776 KB |
Output is correct |
14 |
Correct |
20 ms |
82776 KB |
Output is correct |
15 |
Correct |
19 ms |
82716 KB |
Output is correct |
16 |
Correct |
19 ms |
82520 KB |
Output is correct |
17 |
Correct |
20 ms |
82768 KB |
Output is correct |
18 |
Correct |
19 ms |
82780 KB |
Output is correct |
19 |
Correct |
19 ms |
82656 KB |
Output is correct |
20 |
Correct |
20 ms |
82776 KB |
Output is correct |
21 |
Correct |
20 ms |
82780 KB |
Output is correct |
22 |
Correct |
20 ms |
82776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
82520 KB |
Output is correct |
2 |
Correct |
812 ms |
138032 KB |
Output is correct |
3 |
Correct |
810 ms |
141348 KB |
Output is correct |
4 |
Correct |
678 ms |
100828 KB |
Output is correct |
5 |
Correct |
818 ms |
136408 KB |
Output is correct |
6 |
Correct |
799 ms |
136652 KB |
Output is correct |
7 |
Correct |
697 ms |
101328 KB |
Output is correct |
8 |
Correct |
687 ms |
101460 KB |
Output is correct |
9 |
Correct |
685 ms |
99752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
82524 KB |
Output is correct |
2 |
Correct |
702 ms |
99684 KB |
Output is correct |
3 |
Correct |
693 ms |
100220 KB |
Output is correct |
4 |
Correct |
694 ms |
100192 KB |
Output is correct |
5 |
Correct |
695 ms |
103636 KB |
Output is correct |
6 |
Correct |
697 ms |
99640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
992 ms |
166520 KB |
Output is correct |
2 |
Correct |
966 ms |
169912 KB |
Output is correct |
3 |
Correct |
979 ms |
167292 KB |
Output is correct |
4 |
Correct |
971 ms |
166932 KB |
Output is correct |
5 |
Correct |
872 ms |
150352 KB |
Output is correct |
6 |
Correct |
861 ms |
150168 KB |
Output is correct |
7 |
Correct |
760 ms |
144212 KB |
Output is correct |
8 |
Correct |
764 ms |
142684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
82520 KB |
Output is correct |
2 |
Correct |
17 ms |
82524 KB |
Output is correct |
3 |
Correct |
17 ms |
82524 KB |
Output is correct |
4 |
Correct |
18 ms |
82968 KB |
Output is correct |
5 |
Correct |
18 ms |
82700 KB |
Output is correct |
6 |
Correct |
18 ms |
82524 KB |
Output is correct |
7 |
Correct |
17 ms |
82524 KB |
Output is correct |
8 |
Correct |
18 ms |
82524 KB |
Output is correct |
9 |
Correct |
19 ms |
82676 KB |
Output is correct |
10 |
Correct |
18 ms |
82656 KB |
Output is correct |
11 |
Correct |
18 ms |
82520 KB |
Output is correct |
12 |
Correct |
17 ms |
82520 KB |
Output is correct |
13 |
Correct |
20 ms |
82776 KB |
Output is correct |
14 |
Correct |
20 ms |
82776 KB |
Output is correct |
15 |
Correct |
19 ms |
82716 KB |
Output is correct |
16 |
Correct |
19 ms |
82520 KB |
Output is correct |
17 |
Correct |
20 ms |
82768 KB |
Output is correct |
18 |
Correct |
19 ms |
82780 KB |
Output is correct |
19 |
Correct |
19 ms |
82656 KB |
Output is correct |
20 |
Correct |
20 ms |
82776 KB |
Output is correct |
21 |
Correct |
20 ms |
82780 KB |
Output is correct |
22 |
Correct |
20 ms |
82776 KB |
Output is correct |
23 |
Correct |
154 ms |
91260 KB |
Output is correct |
24 |
Correct |
149 ms |
91380 KB |
Output is correct |
25 |
Correct |
153 ms |
91476 KB |
Output is correct |
26 |
Correct |
132 ms |
86516 KB |
Output is correct |
27 |
Correct |
130 ms |
86356 KB |
Output is correct |
28 |
Correct |
126 ms |
86352 KB |
Output is correct |
29 |
Correct |
112 ms |
85148 KB |
Output is correct |
30 |
Correct |
115 ms |
85076 KB |
Output is correct |
31 |
Correct |
111 ms |
85708 KB |
Output is correct |
32 |
Correct |
128 ms |
95972 KB |
Output is correct |
33 |
Correct |
149 ms |
90456 KB |
Output is correct |
34 |
Correct |
149 ms |
90600 KB |
Output is correct |
35 |
Correct |
146 ms |
90164 KB |
Output is correct |
36 |
Correct |
148 ms |
90208 KB |
Output is correct |
37 |
Correct |
146 ms |
90196 KB |
Output is correct |
38 |
Correct |
145 ms |
90412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
82520 KB |
Output is correct |
2 |
Correct |
17 ms |
82524 KB |
Output is correct |
3 |
Correct |
17 ms |
82524 KB |
Output is correct |
4 |
Correct |
18 ms |
82968 KB |
Output is correct |
5 |
Correct |
18 ms |
82700 KB |
Output is correct |
6 |
Correct |
18 ms |
82524 KB |
Output is correct |
7 |
Correct |
17 ms |
82524 KB |
Output is correct |
8 |
Correct |
18 ms |
82524 KB |
Output is correct |
9 |
Correct |
19 ms |
82676 KB |
Output is correct |
10 |
Correct |
18 ms |
82656 KB |
Output is correct |
11 |
Correct |
18 ms |
82520 KB |
Output is correct |
12 |
Correct |
17 ms |
82520 KB |
Output is correct |
13 |
Correct |
20 ms |
82776 KB |
Output is correct |
14 |
Correct |
20 ms |
82776 KB |
Output is correct |
15 |
Correct |
19 ms |
82716 KB |
Output is correct |
16 |
Correct |
19 ms |
82520 KB |
Output is correct |
17 |
Correct |
20 ms |
82768 KB |
Output is correct |
18 |
Correct |
19 ms |
82780 KB |
Output is correct |
19 |
Correct |
19 ms |
82656 KB |
Output is correct |
20 |
Correct |
20 ms |
82776 KB |
Output is correct |
21 |
Correct |
20 ms |
82780 KB |
Output is correct |
22 |
Correct |
20 ms |
82776 KB |
Output is correct |
23 |
Correct |
812 ms |
138032 KB |
Output is correct |
24 |
Correct |
810 ms |
141348 KB |
Output is correct |
25 |
Correct |
678 ms |
100828 KB |
Output is correct |
26 |
Correct |
818 ms |
136408 KB |
Output is correct |
27 |
Correct |
799 ms |
136652 KB |
Output is correct |
28 |
Correct |
697 ms |
101328 KB |
Output is correct |
29 |
Correct |
687 ms |
101460 KB |
Output is correct |
30 |
Correct |
685 ms |
99752 KB |
Output is correct |
31 |
Correct |
702 ms |
99684 KB |
Output is correct |
32 |
Correct |
693 ms |
100220 KB |
Output is correct |
33 |
Correct |
694 ms |
100192 KB |
Output is correct |
34 |
Correct |
695 ms |
103636 KB |
Output is correct |
35 |
Correct |
697 ms |
99640 KB |
Output is correct |
36 |
Correct |
992 ms |
166520 KB |
Output is correct |
37 |
Correct |
966 ms |
169912 KB |
Output is correct |
38 |
Correct |
979 ms |
167292 KB |
Output is correct |
39 |
Correct |
971 ms |
166932 KB |
Output is correct |
40 |
Correct |
872 ms |
150352 KB |
Output is correct |
41 |
Correct |
861 ms |
150168 KB |
Output is correct |
42 |
Correct |
760 ms |
144212 KB |
Output is correct |
43 |
Correct |
764 ms |
142684 KB |
Output is correct |
44 |
Correct |
154 ms |
91260 KB |
Output is correct |
45 |
Correct |
149 ms |
91380 KB |
Output is correct |
46 |
Correct |
153 ms |
91476 KB |
Output is correct |
47 |
Correct |
132 ms |
86516 KB |
Output is correct |
48 |
Correct |
130 ms |
86356 KB |
Output is correct |
49 |
Correct |
126 ms |
86352 KB |
Output is correct |
50 |
Correct |
112 ms |
85148 KB |
Output is correct |
51 |
Correct |
115 ms |
85076 KB |
Output is correct |
52 |
Correct |
111 ms |
85708 KB |
Output is correct |
53 |
Correct |
128 ms |
95972 KB |
Output is correct |
54 |
Correct |
149 ms |
90456 KB |
Output is correct |
55 |
Correct |
149 ms |
90600 KB |
Output is correct |
56 |
Correct |
146 ms |
90164 KB |
Output is correct |
57 |
Correct |
148 ms |
90208 KB |
Output is correct |
58 |
Correct |
146 ms |
90196 KB |
Output is correct |
59 |
Correct |
145 ms |
90412 KB |
Output is correct |
60 |
Correct |
1033 ms |
141784 KB |
Output is correct |
61 |
Correct |
1070 ms |
141380 KB |
Output is correct |
62 |
Correct |
1041 ms |
141368 KB |
Output is correct |
63 |
Correct |
818 ms |
104724 KB |
Output is correct |
64 |
Correct |
816 ms |
104724 KB |
Output is correct |
65 |
Correct |
841 ms |
104788 KB |
Output is correct |
66 |
Correct |
701 ms |
100764 KB |
Output is correct |
67 |
Correct |
705 ms |
100716 KB |
Output is correct |
68 |
Correct |
690 ms |
103108 KB |
Output is correct |
69 |
Correct |
783 ms |
170404 KB |
Output is correct |
70 |
Correct |
984 ms |
136732 KB |
Output is correct |
71 |
Correct |
999 ms |
136264 KB |
Output is correct |
72 |
Correct |
975 ms |
133984 KB |
Output is correct |
73 |
Correct |
1016 ms |
135372 KB |
Output is correct |
74 |
Correct |
986 ms |
133484 KB |
Output is correct |
75 |
Correct |
1000 ms |
135620 KB |
Output is correct |