oj.uz

Submission #549464

# Submission time Handle Problem Language Result Execution time Memory
549464 2022-04-15T20:52:18 Z Vladth11 Baloni (COCI15_baloni) C++14
100 / 100
 847 ms 92444 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 1000001;
const ll VMAX = 26;
const ll INF = (1LL << 55);
const ll MOD = 90000000000000001;
const ll BLOCK = 1000000;
const ll base = 1000000001;
const ll nr_of_bits = 18;

set <int> st[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i;
    cin >> n;
    for(i = 1; i <= n; i++){
        int x;
        cin >> x;
        st[x].insert(i);
    }
    int cnt = 0;
    for(i = NMAX - 1; i >= 0; i--){
        for(auto x : st[i]){
            int cc = i - 1;
            int last = x;
            cnt++;
            auto it = st[cc].lower_bound(last);
            while(it != st[cc].end()){
                last = (*it);
                st[cc].erase(it);
                cc--;
                it = st[cc].lower_bound(last);
            }
        }
    }
    cout << cnt;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47280 KB Output is correct
2 Correct 26 ms 47304 KB Output is correct
3 Correct 27 ms 47416 KB Output is correct
4 Correct 31 ms 47440 KB Output is correct
5 Correct 712 ms 88012 KB Output is correct
6 Correct 847 ms 92444 KB Output is correct
7 Correct 632 ms 84468 KB Output is correct
8 Correct 629 ms 83996 KB Output is correct
9 Correct 666 ms 86312 KB Output is correct
10 Correct 691 ms 87652 KB Output is correct