oj.uz

Submission #230993

# Submission time Handle Problem Language Result Execution time Memory
230993 2020-05-12T10:01:20 Z kai824 Baloni (COCI15_baloni) C++17
100 / 100
 1283 ms 93944 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47352 KB Output is correct
2 Correct 33 ms 47360 KB Output is correct
3 Correct 36 ms 47480 KB Output is correct
4 Correct 34 ms 47608 KB Output is correct
5 Correct 1165 ms 91128 KB Output is correct
6 Correct 1283 ms 93944 KB Output is correct
7 Correct 1008 ms 87544 KB Output is correct
8 Correct 1041 ms 86904 KB Output is correct
9 Correct 1168 ms 89368 KB Output is correct
10 Correct 1139 ms 90872 KB Output is correct