#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int nmax = 2 * 1e5 + 7;
struct insula {
int val, ind;
} v[nmax];
int root[nmax], sum[nmax];
bool f[nmax];
bool cmp(insula a, insula b) {
return a.val > b.val;
}
int find(int x) {
if(root[x] == x) {
return x;
}
root[x] = find(root[x]);
return root[x];
}
void unite(int a, int b) {
if(sum[a] < sum[b]) {
swap(a, b);
}
sum[a] += sum[b];
root[b] = a;
}
int32_t main() {
int n, maxx = 0, cnt = 0;
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> v[i].val;
v[i].ind = i;
}
sort(v + 1, v + n + 1, cmp);
for(int i = 1; i <= n; i ++) {
f[v[i].ind] = 1;
if(f[v[i].ind - 1] == 0 && f[v[i].ind + 1] == 0) {
cnt ++;
root[v[i].ind] = v[i].ind;
sum[v[i].ind] = 1;
} else if(f[v[i].ind - 1] == 1 && f[v[i].ind + 1] == 0) {
root[v[i].ind] = v[i].ind;
sum[v[i].ind] = 1;
unite(v[i].ind, find(v[i].ind - 1));
} else if(f[v[i].ind + 1] == 1 && f[v[i].ind - 1] == 0) {
root[v[i].ind] = v[i].ind;
sum[v[i].ind] = 1;
unite(v[i].ind, find(v[i].ind + 1));
} else {
cnt --;
root[v[i].ind] = v[i].ind;
sum[v[i].ind] = 1;
unite(v[i].ind, find(v[i].ind + 1));
unite(find(v[i].ind), find(v[i].ind - 1));
}
maxx = max(maxx, cnt);
}
cout << maxx;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
312 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
2212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
2748 KB |
Output is correct |
2 |
Correct |
26 ms |
2476 KB |
Output is correct |
3 |
Correct |
35 ms |
2784 KB |
Output is correct |
4 |
Correct |
43 ms |
2728 KB |
Output is correct |
5 |
Correct |
42 ms |
2676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
57 ms |
5532 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
55 ms |
5444 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |