Submission #230993

#	Time	Username	Problem	Language	Result	Execution time	Memory
230993		kai824	Baloni (COCI15_baloni)	C++17	100 / 100	1283 ms	93944 KiB

baloni

#include"bits/stdc++.h"
using namespace std;

int h[1000005];
set<int> cnt[1000005];

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,cur,ans=0;
    cin>>n;
    for(int x=0;x<n;x++){
      cin>>h[x];
      cnt[h[x]].insert(x);
    }
    for(int x=0;x<n;x++){
      if(h[x]==0)continue;
      ans++;
      cur=x;
      for(int u=h[x]-1;u>0;u--){
        if(cnt[u].lower_bound(cur)==cnt[u].end()){
          break;
        }
        cur= *cnt[u].lower_bound(cur);
        h[cur]=0;
        cnt[u].erase(cur);
      }
      cnt[h[x]].erase(x);
      h[x]=0;
    }
    cout<<ans<<'\n';
    return 0;
}

• Subtask 1: 100 / 100