fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
  5.  
  6. #define endl '\n'
  7.  
  8. #define ff first
  9. #define ss second
  10.  
  11. typedef pair<int, int> ii;
  12. typedef long long ll;
  13.  
  14. signed main(void) {
  15.     FAST_IO;
  16.  
  17.     int n; cin >> n;
  18.     vector<pair<int, bool>> h(n);
  19.     map<int, queue<int>> mp;
  20.  
  21.     for (int i = 0; i < n; i++) {
  22.         int x; cin >> x;
  23.         h[i].ff = x; h[i].ss = false;
  24.         mp[x].push(i);
  25.     }
  26.  
  27.     ll ans = 0;
  28.  
  29.     for(int i = 0; i < n; i++) {
  30.         if (h[i].ss == false) {
  31.             ans++;
  32.             h[i].ss = true;
  33.             mp[h[i].ff].pop();
  34.             int atual = h[i].ff - 1;
  35.             int id_atual = i + 1;
  36.             while (atual >= 1 && id_atual < n) {
  37.                 if (!mp[atual].empty() && mp[atual].front() >= id_atual) {
  38.                     h[mp[atual].front()].ss = true;                        
  39.                     id_atual = mp[atual].front() + 1;
  40.                     mp[atual].pop();
  41.                     atual--;
  42.                 } else {
  43.                     break;
  44.                 }
  45.             }
  46.         }
  47.     }
  48.     cout << ans << endl;
  49. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5348
https://ideone.com/s37c21
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!