Submission #549464

#	Time	Username	Problem	Language	Result	Execution time	Memory
549464		Vladth11	Baloni (COCI15_baloni)	C++14	100 / 100	847 ms	92444 KiB

baloni

#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 / 100