oj.uz

Submission #697180

# Submission time Handle Problem Language Result Execution time Memory
697180 2023-02-08T17:32:26 Z kusssso Baloni (COCI15_baloni) C++17
100 / 100
 781 ms 96008 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47316 KB Output is correct
2 Correct 26 ms 47316 KB Output is correct
3 Correct 26 ms 47432 KB Output is correct
4 Correct 26 ms 47436 KB Output is correct
5 Correct 623 ms 91160 KB Output is correct
6 Correct 781 ms 96008 KB Output is correct
7 Correct 631 ms 87508 KB Output is correct
8 Correct 572 ms 86836 KB Output is correct
9 Correct 599 ms 89360 KB Output is correct
10 Correct 648 ms 90760 KB Output is correct