#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MAX = 1e5 + 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;
while(r - l > 1) {
int mid = l + r >> 1;
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:105:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16988 KB |
Output is correct |
2 |
Correct |
4 ms |
16988 KB |
Output is correct |
3 |
Correct |
4 ms |
16988 KB |
Output is correct |
4 |
Correct |
4 ms |
16988 KB |
Output is correct |
5 |
Correct |
6 ms |
16824 KB |
Output is correct |
6 |
Correct |
3 ms |
16988 KB |
Output is correct |
7 |
Correct |
4 ms |
16988 KB |
Output is correct |
8 |
Correct |
4 ms |
16988 KB |
Output is correct |
9 |
Correct |
4 ms |
16988 KB |
Output is correct |
10 |
Correct |
4 ms |
16988 KB |
Output is correct |
11 |
Correct |
4 ms |
17048 KB |
Output is correct |
12 |
Correct |
4 ms |
16988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16988 KB |
Output is correct |
2 |
Correct |
4 ms |
16988 KB |
Output is correct |
3 |
Correct |
4 ms |
16988 KB |
Output is correct |
4 |
Correct |
4 ms |
16988 KB |
Output is correct |
5 |
Correct |
6 ms |
16824 KB |
Output is correct |
6 |
Correct |
3 ms |
16988 KB |
Output is correct |
7 |
Correct |
4 ms |
16988 KB |
Output is correct |
8 |
Correct |
4 ms |
16988 KB |
Output is correct |
9 |
Correct |
4 ms |
16988 KB |
Output is correct |
10 |
Correct |
4 ms |
16988 KB |
Output is correct |
11 |
Correct |
4 ms |
17048 KB |
Output is correct |
12 |
Correct |
4 ms |
16988 KB |
Output is correct |
13 |
Correct |
6 ms |
17240 KB |
Output is correct |
14 |
Correct |
8 ms |
17244 KB |
Output is correct |
15 |
Correct |
6 ms |
16984 KB |
Output is correct |
16 |
Correct |
8 ms |
16984 KB |
Output is correct |
17 |
Correct |
6 ms |
16984 KB |
Output is correct |
18 |
Correct |
6 ms |
17244 KB |
Output is correct |
19 |
Correct |
6 ms |
17240 KB |
Output is correct |
20 |
Correct |
6 ms |
16988 KB |
Output is correct |
21 |
Correct |
6 ms |
16988 KB |
Output is correct |
22 |
Correct |
7 ms |
16988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16988 KB |
Output is correct |
2 |
Runtime error |
56 ms |
42548 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16988 KB |
Output is correct |
2 |
Runtime error |
61 ms |
43344 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
60 ms |
42580 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16988 KB |
Output is correct |
2 |
Correct |
4 ms |
16988 KB |
Output is correct |
3 |
Correct |
4 ms |
16988 KB |
Output is correct |
4 |
Correct |
4 ms |
16988 KB |
Output is correct |
5 |
Correct |
6 ms |
16824 KB |
Output is correct |
6 |
Correct |
3 ms |
16988 KB |
Output is correct |
7 |
Correct |
4 ms |
16988 KB |
Output is correct |
8 |
Correct |
4 ms |
16988 KB |
Output is correct |
9 |
Correct |
4 ms |
16988 KB |
Output is correct |
10 |
Correct |
4 ms |
16988 KB |
Output is correct |
11 |
Correct |
4 ms |
17048 KB |
Output is correct |
12 |
Correct |
4 ms |
16988 KB |
Output is correct |
13 |
Correct |
6 ms |
17240 KB |
Output is correct |
14 |
Correct |
8 ms |
17244 KB |
Output is correct |
15 |
Correct |
6 ms |
16984 KB |
Output is correct |
16 |
Correct |
8 ms |
16984 KB |
Output is correct |
17 |
Correct |
6 ms |
16984 KB |
Output is correct |
18 |
Correct |
6 ms |
17244 KB |
Output is correct |
19 |
Correct |
6 ms |
17240 KB |
Output is correct |
20 |
Correct |
6 ms |
16988 KB |
Output is correct |
21 |
Correct |
6 ms |
16988 KB |
Output is correct |
22 |
Correct |
7 ms |
16988 KB |
Output is correct |
23 |
Correct |
139 ms |
26196 KB |
Output is correct |
24 |
Correct |
137 ms |
25964 KB |
Output is correct |
25 |
Correct |
138 ms |
26124 KB |
Output is correct |
26 |
Correct |
113 ms |
20840 KB |
Output is correct |
27 |
Correct |
116 ms |
20820 KB |
Output is correct |
28 |
Correct |
113 ms |
20788 KB |
Output is correct |
29 |
Correct |
101 ms |
19580 KB |
Output is correct |
30 |
Correct |
99 ms |
19708 KB |
Output is correct |
31 |
Correct |
108 ms |
20424 KB |
Output is correct |
32 |
Correct |
111 ms |
30780 KB |
Output is correct |
33 |
Correct |
136 ms |
25256 KB |
Output is correct |
34 |
Correct |
135 ms |
25168 KB |
Output is correct |
35 |
Correct |
130 ms |
24800 KB |
Output is correct |
36 |
Correct |
134 ms |
24904 KB |
Output is correct |
37 |
Correct |
138 ms |
24924 KB |
Output is correct |
38 |
Correct |
143 ms |
25344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16988 KB |
Output is correct |
2 |
Correct |
4 ms |
16988 KB |
Output is correct |
3 |
Correct |
4 ms |
16988 KB |
Output is correct |
4 |
Correct |
4 ms |
16988 KB |
Output is correct |
5 |
Correct |
6 ms |
16824 KB |
Output is correct |
6 |
Correct |
3 ms |
16988 KB |
Output is correct |
7 |
Correct |
4 ms |
16988 KB |
Output is correct |
8 |
Correct |
4 ms |
16988 KB |
Output is correct |
9 |
Correct |
4 ms |
16988 KB |
Output is correct |
10 |
Correct |
4 ms |
16988 KB |
Output is correct |
11 |
Correct |
4 ms |
17048 KB |
Output is correct |
12 |
Correct |
4 ms |
16988 KB |
Output is correct |
13 |
Correct |
6 ms |
17240 KB |
Output is correct |
14 |
Correct |
8 ms |
17244 KB |
Output is correct |
15 |
Correct |
6 ms |
16984 KB |
Output is correct |
16 |
Correct |
8 ms |
16984 KB |
Output is correct |
17 |
Correct |
6 ms |
16984 KB |
Output is correct |
18 |
Correct |
6 ms |
17244 KB |
Output is correct |
19 |
Correct |
6 ms |
17240 KB |
Output is correct |
20 |
Correct |
6 ms |
16988 KB |
Output is correct |
21 |
Correct |
6 ms |
16988 KB |
Output is correct |
22 |
Correct |
7 ms |
16988 KB |
Output is correct |
23 |
Runtime error |
56 ms |
42548 KB |
Execution killed with signal 11 |
24 |
Halted |
0 ms |
0 KB |
- |