Submission #1191506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191506		a0ms1n	Global Warming (NOI13_gw)	C++20	40 / 40	429 ms	31696 KiB

gw

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11