Submission #1124111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124111		kustizus	Ball Machine (BOI13_ballmachine)	C++20	16.11 / 100	481 ms	33816 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define sz(s) (int)s.size()
#define bit(i, j) ((j >> i) & 1)
#define all(v) v.begin(), v.end()
#define taskname "file"

typedef long long ll;

const int N = 1e5;
int n, q, idx = 0, in[N + 5], ou[N + 5], p[N + 5], lz[4 * N + 5], pa[N + 5][20], depth[N + 5], st[20][N + 5], pp[N + 5];
vector <int> order, g[N + 5];

struct node{
    int cnt0, cnt1;
} sg[4 * N + 5];

void dfs(int i){
    for(int j : g[i]){
        pa[j][0] = i;
        depth[j] = depth[i] + 1;
        for (int k = 1; k < 20; ++k)
            pa[j][k] = pa[pa[j][k - 1]][k - 1];
        dfs(j);
        in[i] = (!in[i] ? in[j] : min(in[i], in[j]));
    }
    order.push_back(i);
    ou[i] = ++idx;
    pp[idx] = i;
    if (!in[i]) in[i] = idx;
}

void build1(){
    for (int i = 1; i <= n; ++i) st[0][i] = ou[order[i - 1]];
    for (int i = 1; i < 20; ++i)
        for (int j = 1; j <= n - (1 << i) + 1; ++j)
            st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}

int getmin(int l, int r){
    int b = __lg(r - l + 1);
    return pp[max(st[b][l], st[b][r - (1 << b) + 1])];
}

int parent(int i, int p){
    for (int k = 19; k >= 0; --k)
        if (p >= (1 << k)){
            p -= (1 << k);
            i = pa[i][k];
        }
    return i;
}

node mer(node a, node b){
    a.cnt0 += b.cnt0;
    a.cnt1 += b.cnt1;
    return a;
}

void build(int id, int l, int r){
    lz[id] = -1;
    sg[id] = {r - l + 1, 0};
    if (l == r) return;
    int md = (l + r) >> 1;
    build(id << 1, l, md);
    build(id << 1 | 1, md + 1, r);
}

void pus(int id, int l, int r){
    if (lz[id] == -1) return;
    if (l != r){
        lz[id << 1] = lz[id << 1 | 1] = lz[id];
    }
    if (lz[id]) sg[id] = {0, r - l + 1};
    else sg[id] = {r - l + 1, 0};
    lz[id] = -1;
}

void update(int id, int l, int r, int x, int y, int val){
    pus(id, l, r);
    if (l > y || r < x) return;
    if (l >= x && r <= y){
        lz[id] = val;
        pus(id, l, r);
        return;
    }
    int md = (l + r) >> 1;
    update(id << 1, l, md, x, y, val);
    update(id << 1 | 1, md + 1, r, x, y, val);
    sg[id] = mer(sg[id << 1], sg[id << 1 | 1]);
}

int get(int id, int l, int r, int pos){
    pus(id, l, r);
    if (l > pos || r < pos) return 0;
    if (l == r) return sg[id].cnt1;
    int md = (l + r) >> 1;
    return get(id << 1, l, md, pos) + get(id << 1 | 1, md + 1, r, pos);
}

int walk(int id, int l, int r, int val){
    pus(id, l, r);
    if (l == r) return l;
    int md = (l + r) >> 1;
    pus(id << 1, l, md);
    pus(id << 1 | 1, md + 1, r);
    if (sg[id << 1].cnt0 >= val) return walk(id << 1, l, md, val);
    return walk(id << 1 | 1, md + 1, r, val - sg[id << 1].cnt0);
}

bool check(int x, int len){
    int p = parent(x, len);
    if (get(1, 1, n, ou[p])) return true;
    return false;
}

void solve(){
    cin >> n >> q;
    int root = 0;
    for (int i = 1; i <= n; ++i){
        cin >> p[i];
        g[p[i]].push_back(i);
        if (!p[i]) root = i;
    }
    for (int i = 1; i <= n; ++i) sort(all(g[i]));
    depth[root] = 1;
    dfs(root);
    build(1, 1, n);
    build1();
    while (q--){
        int ty, x;
        cin >> ty >> x;
        if (ty == 1){
            int d = walk(1, 1, n, x);
            cout << getmin(1, d) << "\n";
            update(1, 1, n, 1, d, 1);
        }
        else{
            int l = 0, r = depth[x] - 1;
            while (l < r){
                int md = (l + r) >> 1;
                if (check(x, md + 1)) l = md + 1;
                else r = md;
            }
            cout << l << "\n";
            int p = parent(x, l);
            update(1, 1, n, ou[p], ou[p], 0);
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen(taskname".inp", "r", stdin);
    // freopen(taskname".out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
}

• Subtask 1: 0 / 25
• Subtask 2: 6.4286 / 30
• Subtask 3: 8.5714 / 40
• Subtask 4: 1.1111 / 5