oj.uz

Submission #251682

# Submission time Handle Problem Language Result Execution time Memory
251682 2020-07-22T07:18:47 Z VEGAnn Baloni (COCI15_baloni) C++14
0 / 100
 2000 ms 96560 KB 
#include <bits/stdc++.h>
#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<int> ps[N];
set<int>::iterator iter;
int n, a[N], ans, nm[N];
bool mrk[N];

int mult(int x, int y) { return (x * y) % md; }

void SUM(int &x, int y){
    x += y;
    if (x >= md)
        x -= md;
}

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);
#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[a[i]].insert(i);

    int ptr = 1;

    while (1){
        while (ptr <= n && mrk[nm[ptr]])
            ptr++;

        if (ptr > n) break;

        ans++;

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

        while (pst != 0){
            if (sz(ps[vl - 1]) == 0) break;

            iter = ps[vl - 1].upper_bound(pst);

            if (iter == ps[vl - 1].end()) break;

            ps[vl - 1].erase(iter);

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

    cout << ans;

    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 47360 KB Time limit exceeded
2 Execution timed out 2090 ms 47488 KB Time limit exceeded
3 Execution timed out 2089 ms 47488 KB Time limit exceeded
4 Execution timed out 2091 ms 47616 KB Time limit exceeded
5 Execution timed out 2095 ms 91512 KB Time limit exceeded
6 Execution timed out 2095 ms 96560 KB Time limit exceeded
7 Execution timed out 2095 ms 87928 KB Time limit exceeded
8 Execution timed out 2056 ms 87480 KB Time limit exceeded
9 Execution timed out 2093 ms 89848 KB Time limit exceeded
10 Execution timed out 2101 ms 91512 KB Time limit exceeded