Submission #1191506

#TimeUsernameProblemLanguageResultExecution timeMemory
1191506a0ms1n지구 온난화 (NOI13_gw)C++20
40 / 40
429 ms31696 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

pair<int,int> arr[(int)1e6+1];
int parent[(int)1e6+1]={0};
int used[(int)1e6+1]={0};

int find(int a){
    if(a==parent[a])return a;
    return parent[a] = find(parent[a]);
}

int cnt = 0;

void combine(int a,int b){
    if(find(a)==find(b))return;
    parent[find(a)] = find(b);
    cnt--;
}

signed main(){
    int x;
    int n;cin>>n;
    iota(parent,parent+n+1,0);
    for(int i=0;i<n;i++)cin>>x,arr[i]={x,i};
    sort(arr,arr+n,greater<pair<int,int>>());
    int mx = 0;
    for(int i=0;i<n;i++){
        int f = arr[i].first;
        while(i<n && arr[i].first == f){
            int idx = arr[i].second;
            used[idx] = 1;
            cnt++;
            if(idx-1>=0 && used[idx-1]){
                combine(idx,idx-1);
            }   
            if(idx+1<n && used[idx+1]){
                combine(idx,idx+1);
            }
            i++;
        }
        i--;
        mx = max(mx,cnt);
    }
    cout<<mx;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...