oj.uz

Submission #253095

# Submission time Handle Problem Language Result Execution time Memory
253095 2020-07-26T22:01:30 Z Sprdalo Baloni (COCI15_baloni) C++17
100 / 100
 1164 ms 92528 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47360 KB Output is correct
2 Correct 32 ms 47480 KB Output is correct
3 Correct 34 ms 47480 KB Output is correct
4 Correct 33 ms 47616 KB Output is correct
5 Correct 1008 ms 88312 KB Output is correct
6 Correct 1164 ms 92528 KB Output is correct
7 Correct 985 ms 84600 KB Output is correct
8 Correct 948 ms 84216 KB Output is correct
9 Correct 1035 ms 86520 KB Output is correct
10 Correct 1070 ms 87928 KB Output is correct