oj.uz

Submission #251848

# Submission time Handle Problem Language Result Execution time Memory
251848 2020-07-22T11:20:51 Z VEGAnn Baloni (COCI15_baloni) C++14
100 / 100
 1432 ms 50936 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define sz(x) ((int)x.size())
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int N = 1000100;
const int C = 22;
const int md = 10007;
set<i2> ps;
set<i2>::iterator iter;
int n, a[N], ans, nm[N];
bool mrk[N];

bool cmp(int _x, int _y){
    if (a[_x] == a[_y])
        return _x < _y;
    else return a[_x] > a[_y];
}

int main() {
#ifdef _LOCAL
//    freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
    freopen("5.in","r",stdin); // freopen("output.txt","w",stdout);
#else
//    freopen("mining.in","r",stdin); freopen("mining.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        nm[i] = i;
    }

    sort(nm + 1, nm + n + 1, cmp);

    for (int i = n; i > 0; i--)
        ps.insert({a[i], i});

    int ptr = 1;

    while (1){
        while (ptr <= n && mrk[nm[ptr]]) {
            if (ptr == 660155)
                cerr << ptr << '\n';

            ptr++;
        }

        if (ptr > n) break;

        ans++;

        int pst = nm[ptr], vl = a[nm[ptr]];

        mrk[pst] = 1;

        while (pst != 0){
            if (sz(ps) == 0) break;

            iter = ps.upper_bound({vl - 1, pst});

            if (iter == ps.end()) break;

            if ((*iter)[0] != vl - 1) break;

            ps.erase(iter);

            pst = (*iter)[1];

            assert(pst > 0);

            vl--;
            mrk[pst] = 1;
        }
    }

    cout << ans;

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 1223 ms 45500 KB Output is correct
6 Correct 1432 ms 50936 KB Output is correct
7 Correct 1129 ms 42232 KB Output is correct
8 Correct 1111 ms 41720 KB Output is correct
9 Correct 1231 ms 43900 KB Output is correct
10 Correct 1256 ms 45560 KB Output is correct