Submission #154217

#	Time	Username	Problem	Language	Result	Execution time	Memory
154217		KCSC	Baloni (COCI15_baloni)	C++14	100 / 100	986 ms	23772 KiB

baloni

#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 / 100