oj.uz

Submission #154217

# Submission time Handle Problem Language Result Execution time Memory
154217 2019-09-19T10:59:50 Z KCSC Baloni (COCI15_baloni) C++14
100 / 100
 986 ms 23772 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 1000005;

int arr[DIM];
pair<int, int> sgt[DIM * 4];

pair<int, int> updateNode(pair<int, int> p1, pair<int, int> p2) {
    if (p1.first > p2.first)
        return p1;
    else
        return p2;
}

void build(int nd, int le, int ri) {
    if (le == ri)
        sgt[nd] = make_pair(arr[le], le);
    else {
        int md = (le + ri) / 2;
        build(nd * 2, le, md);
        build(nd * 2 + 1, md + 1, ri);
        sgt[nd] = updateNode(sgt[nd * 2], sgt[nd * 2 + 1]);
    }
}

void update(int nd, int le, int ri, int ps, int vl) {
    if (le == ri)
        sgt[nd] = make_pair(vl, le);
    else {
        int md = (le + ri) / 2;
        if (ps <= md)
            update(nd * 2, le, md, ps, vl);
        else
            update(nd * 2 + 1, md + 1, ri, ps, vl);
        sgt[nd] = updateNode(sgt[nd * 2], sgt[nd * 2 + 1]);
    }
}

pair<int, int> query(int nd, int le, int ri, int st, int en) {
    if (en < le || ri < st)
        return make_pair(-1, -1);
    if (st <= le && ri <= en)
        return sgt[nd];
    else {
        int md = (le + ri) / 2;
        return updateNode(query(nd * 2, le, md, st, en),
                          query(nd * 2 + 1, md + 1, ri, st, en));
    }
}

int main(void) {
  //  freopen("c.in", "r", stdin);
  //  freopen("c.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i];
    build(1, 1, n);
    int ans = 0;
    while (sgt[1].first != 0) {
        int h = sgt[1].first, p = 1;
        ++ans;
        while (true) {
            if (p > n)
                break;
            pair<int, int> pr = query(1, 1, n, p, n);
            if (pr.first != h)
                break;
            update(1, 1, n, pr.second, 0);
            p = pr.second + 1;
            --h;
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 899 ms 23572 KB Output is correct
6 Correct 986 ms 23772 KB Output is correct
7 Correct 803 ms 22648 KB Output is correct
8 Correct 776 ms 22520 KB Output is correct
9 Correct 824 ms 23068 KB Output is correct
10 Correct 854 ms 23064 KB Output is correct