Submission #872099

#	Time	Username	Problem	Language	Result	Execution time	Memory
872099		sleepntsheep	Ball Machine (BOI13_ballmachine)	C++17	80.15 / 100	454 ms	18004 KiB

ballmachine

#include <iostream>
#include <cassert>
#include <queue>
#include <bitset>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <functional>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200000

int root, n, q, L[N], J[N], P[N], ne, h[N], tout[N], rv[N], timer, t[N<<1], low[N];
char lz[N];
pair<int, int> g[N];

inline void push(int v, int l, int r)
{
    if (-1 == lz[v]) return;
    t[v] = lz[v] * (r-l+1);
    if (l != r) 
    {
        int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2;
        lz[vl] = lz[vr] = lz[v];
    }
    lz[v] = -1;
}

int qry(int x, int y, int v = 0, int l = 0, int r = n - 1)
{
    push(v, l, r);
    if (y < l || r < x) return 0;
    if (x <= l && r <= y) return t[v];
    int m = (l+r)/2, vl =v + 1, vr=v+(m-l+1)*2;
    return qry(x, y, vl, l, m) + qry(x, y, vr, m+1, r);
}

inline int qry(int u) { return qry(tout[u], tout[u]); }

void update(int x, int y, int k, int v = 0, int l = 0, int r = n - 1)
{
    push(v, l, r);
    if (y < l || r < x) return;
    int m = (l+r)/2, vl =v + 1, vr=v+(m-l+1)*2;
    if (x <= l && r <= y) {lz[v] = k; push(v, l, r); return; }
    update(x, y, k, vl, l, m), update(x, y, k, vr, m+1, r);
    t[v] = t[vl]+t[vr];
}

void init()
{
    int Tin[N]{0}, Tout[N]{0}, timer = 0, t[N<<1]{0};
    for (int i = 0; i < 2*n; ++i) t[i] = 1e9;

    function<void(int)> dfs = [&](int u)
    {
        t[n + (Tin[u] = timer++)] = u;
        for (auto j = h[u]; j < ne && g[j].first == u; ++j)
            dfs(g[j].second);
        Tout[u] = timer - 1;
    };
    dfs(root);
    for (int i = n; i--;) t[i] = min(t[i<<1], t[i<<1|1]);
    auto qry = [&](int l, int r)
    {
        int z{100000000};
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
        {
            if (l&1) z = min(z, t[l++]);
            if (r&1) z = min(t[--r], z);
        }
        return z;
    };
    for (int i = 0; i < n; ++i) low[i] = qry(Tin[i], Tout[i]);
}

void dfs(int u)
{
    for (auto j = h[u]; j < ne && g[j].first == u; ++j)
    {
        P[g[j].second] = u;
        if (L[u] - L[J[u]] == L[J[u]] - L[J[J[u]]]) J[g[j].second] = J[J[u]];
        else J[g[j].second] = u;
        L[g[j].second] = L[u] + 1;
        dfs(g[j].second);
    }
    rv[tout[u] = timer++] = u;
}

inline int highest(int u)
{
    for (; u != P[u]; )
    {
        if (qry(J[u])) u = J[u];
        else if (qry(P[u])) u = P[u];
        else break;
    }
    return u;
}

int main()
{
    ShinLena;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> P[i], (P[i] ? void(g[ne++] = {P[i]-1, i}) : void(root = i));
    sort(g, g+ne);
    for (int i = 0; i < n; ++i) if (!i || g[i].first != g[i-1].first) h[g[i].first] = i;

    init();

    sort(g, g+ne, [](const auto &a, const auto &b){
            if (a.first != b.first) return a.first < b.first;
            return low[a.second] < low[b.second];
    });

    for (int i = 0; i < ne; ++i) if (!i || g[i].first != g[i-1].first) h[g[i].first] = i;

    P[root] = root; J[root] = root;
    dfs(root);

    memset(lz, -1, sizeof lz);
    for (int t, k; q--;)
    {
        cin >> t >> k;
        if (t == 1)
        {
            int l = 0, r = n - 1;
            while (l <= r)
            {
                int m = (l+r)/2;
                if (m + 1 - qry(0, m) <= k) l = m + 1;
                else r = m - 1;
            }
            cout << rv[l-1] + 1 << '\n';
            update(0, l-1, 1);
        }
        else
        {
            int r = highest(k-1);
            if (P[r] != r) assert(!qry(P[r]));
            update(tout[r], tout[r], 0);
            cout << L[k-1] - L[r] << '\n';
        }
    }

    return 0;
}

• Subtask 1: 15.384615384615385 / 25
• Subtask 2: 21.428571428571427 / 30
• Subtask 3: 40 / 40
• Subtask 4: 3.3333333333333335 / 5