This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)
#define left le
using namespace std;
typedef long long ll;
const int N = 1e6 + 2;
int n, left[N];
vector <pair <int, int> > a;
int get1(int u){
if(left[u]==-1) return -1;
if(left[u]==u) return u;
left[u] = get1(left[u]);
return left[u];
}
int main(){
ios_base::sync_with_stdio(0);
cin >> n;
f1(i, n){
int x; cin >> x;
a.emplace_back(x, i);
left[i] = -1;
}
sort(a.begin(), a.end(), greater <pair <int, int> > ());
int cur = 0, res = 0;
for(int i = 0; i < n; i++){
int j = i;
if(a[i].first==0) continue;
for(j = i; j < n; j++){
if(a[j].first != a[i].first) break;
int u = a[j].second;
left[u] = u;
int k1 = get1(u - 1), k2 = get1(u + 1);
if(k1 > 0 && k2 > 0){
left[k2] = k1;
left[u] = k1;
cur--;
}
else if(k2 > 0){
left[k2] = u;
}
else if(k1 > 0){
left[u] = k1;
}
else cur++;
}
res = max(res, cur);
i = j - 1;
}
cout << res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |