Submission #253095

#	Time	Username	Problem	Language	Result	Execution time	Memory
253095		Sprdalo	Baloni (COCI15_baloni)	C++17	100 / 100	1164 ms	92528 KiB

baloni

#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

set<int> s[1000010];
set<int> m;

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n, sol = 0;
    cin >> n;

    for (int i = 0; i < n; ++i){
        int x;
        cin >> x;

        s[x].insert(i);
        m.insert(-x);
    }

    while(1){
        if (m.empty()) break;
        ++sol;
        int h = -1 * *m.begin(), l = -1;

        while(1){
            auto it = s[h].upper_bound(l);

            if (it == s[h].end()) break;
            int ind = *it;

            s[h].erase(ind);

            if (s[h].empty()){
                m.erase(-h);
            }

            --h;
            l = ind;
        }
    }

    cout << sol << '\n';
}

• Subtask 1: 100 / 100