Submission #697180

#	Time	Username	Problem	Language	Result	Execution time	Memory
697180		kusssso	Baloni (COCI15_baloni)	C++17	100 / 100	781 ms	96008 KiB

baloni

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
int n;
int h[N];
int pop[N];
set<int> pos[N];

signed main() {
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cin >> n;
      for (int i = 1; i <= n; i++) {
            cin >> h[i];
            pos[h[i]].insert(i);
      }
      int ans = 0;
      for (int i = N - 1; i >= 1; i--) {
            for (auto p : pos[i]) {
                  ++ans;
                  int x = i - 1;
                  while (x > 0) {
                        auto it = pos[x].upper_bound(p);
                        if (it == pos[x].end()) break;
                        p = *it;
                        pos[x].erase(it);
                        x--;
                  }
            }
      }
      cout << ans;
      return 0;
}

• Subtask 1: 100 / 100