oj.uz

Submission #873346

# Submission time Handle Problem Language Result Execution time Memory
873346 2023-11-14T21:40:09 Z tvladm2009 Baloni (COCI15_baloni) C++14
100 / 100
 711 ms 92568 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 7;

set<int> s[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        s[x].insert(i);
    }
    int ans = 0;
    for (int i = N - 1; i >= 0; --i) {
        for (auto pos : s[i]) {
            int h = i - 1;
            int last = pos;
            ans++;
            auto it = s[h].lower_bound(pos);
            while (it != s[h].end()) {
                last = *it;
                s[h].erase(it);
                h--;
                it = s[h].lower_bound(last);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 47452 KB Output is correct
2 Correct 14 ms 47452 KB Output is correct
3 Correct 14 ms 47536 KB Output is correct
4 Correct 14 ms 47448 KB Output is correct
5 Correct 587 ms 88392 KB Output is correct
6 Correct 711 ms 92568 KB Output is correct
7 Correct 593 ms 84596 KB Output is correct
8 Correct 607 ms 84448 KB Output is correct
9 Correct 572 ms 86564 KB Output is correct
10 Correct 634 ms 87768 KB Output is correct