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>
using namespace std;
#define pb push_back
#define ll int
#define pll pair<ll, ll>
#define FOR(i, a, b) for (signed ll i = (signed ll)(a); i < (signed ll)(b); i++)
#define NEGFOR(i, a, b) for (ll i = (a); i > (b); i--)
#define vll vector<ll>
#define sll set<ll>
#define ld long double
#define inf 10000000000
#define mll multiset<ll>
#define vpll vector<pll>
#define nn << "\n"
#define ss << " "
//10^8 operations per second
//greatest int is 2,147,483,647
//greates long long is 9.22337204e18
//ALL FUNCTIONS SHOULD BE LL!!!!
vll parent(1000005),sz(1000005);
void make_set(ll v) {
parent[v] = v;
sz[v] = 1;
}
ll find_set(ll v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void unite(ll a, ll b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (sz[a] < sz[b])
swap(a, b);
parent[b] = a;
sz[a] += sz[b];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n; cin>>n;
vpll v(n);
FOR(i,0,n){
cin>>v[i].first; v[i].second=i+1;
}
sort(v.rbegin(),v.rend());
vector<bool> risen(n+5);
ll curr=0,ans=-1;
FOR(i,0,n){
make_set(v[i].second);
curr++;
risen[v[i].second]=1;
if (risen[v[i].second-1]){
unite(v[i].second-1,v[i].second); --curr;
}
if (risen[v[i].second+1]){
unite(v[i].second+1,v[i].second);--curr;
}
if (i+1<n&&v[i+1].second==v[i].second) continue;
ans=max(ans,curr);
}
cout<<ans;
}
# | 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... |