oj.uz

Submission #872107

# Submission time Handle Problem Language Result Execution time Memory
872107 2023-11-12T10:18:14 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 439 ms 17580 KB 
#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 100000

int root, n, q, L[N], J[N], P[N], tout[N], rv[N], timer, t[N<<1], low[N];
char lz[N<<1];
vector<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;
    if (x <= l && r <= y) {lz[v] = k; push(v, l, r); return; }
    int m = (l+r)/2, vl =v + 1, vr=v+(m-l+1)*2;
    update(x, y, k, vl, l, m), update(x, y, k, vr, m+1, r);
    t[v] = t[vl] + t[vr];
}

void init()
{
    ShinLena;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> P[i], (P[i] ? void(g[P[i]-1].push_back(i)) : void(root = i));

    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 v : g[u]) dfs(v);
        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]);

    for (int i = 0; i < n; ++i) sort(ALL(g[i]), [](int a, int b){ return low[a]<low[b]; });
}

void dfs(int u)
{
    for (auto v : g[u])
    {
        P[v] = u;
        J[v] = (L[u] - L[J[u]] == L[J[u]] - L[J[J[u]]]) ? J[J[u]] : u;
        L[v] = L[u] + 1;
        dfs(v);
    }
    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()
{
    init();

    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;
            }
            update(0, l-1, 1);
            cout << rv[l-1] + 1 << '\n';
        }
        else
        {
            int r = highest(k-1);
            update(tout[r], tout[r], 0);
            cout << L[k-1] - L[r] << '\n';
        }
    }

    return 0;
}

Subtask #1
19.2307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 93 ms 8204 KB Output is correct
3 Correct 77 ms 8548 KB Output is correct
4 Incorrect 2 ms 6236 KB Output isn't correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Incorrect 3 ms 6236 KB Output isn't correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 7 ms 6236 KB Output is correct
10 Correct 18 ms 6768 KB Output is correct
11 Correct 98 ms 8304 KB Output is correct
12 Correct 77 ms 8508 KB Output is correct
13 Incorrect 99 ms 8272 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8284 KB Output is correct
2 Correct 97 ms 12716 KB Output is correct
3 Correct 109 ms 9168 KB Output is correct
4 Correct 51 ms 8284 KB Output is correct
5 Correct 54 ms 8284 KB Output is correct
6 Incorrect 52 ms 8276 KB Output isn't correct
7 Correct 52 ms 7680 KB Output is correct
8 Correct 71 ms 8532 KB Output is correct
9 Correct 83 ms 13144 KB Output is correct
10 Correct 87 ms 12868 KB Output is correct
11 Incorrect 86 ms 12928 KB Output isn't correct
12 Correct 85 ms 11344 KB Output is correct
13 Correct 127 ms 15992 KB Output is correct
14 Correct 109 ms 9088 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 9696 KB Output is correct
2 Correct 252 ms 12076 KB Output is correct
3 Correct 264 ms 15188 KB Output is correct
4 Correct 184 ms 11888 KB Output is correct
5 Correct 153 ms 11604 KB Output is correct
6 Correct 154 ms 11600 KB Output is correct
7 Correct 151 ms 10332 KB Output is correct
8 Correct 263 ms 15160 KB Output is correct
9 Correct 260 ms 13400 KB Output is correct
10 Correct 267 ms 13260 KB Output is correct
11 Correct 260 ms 13136 KB Output is correct
12 Correct 250 ms 11352 KB Output is correct
13 Correct 439 ms 17580 KB Output is correct
14 Correct 85 ms 9164 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 13452 KB Output is correct
2 Correct 243 ms 11404 KB Output is correct
3 Correct 118 ms 17236 KB Output is correct
4 Correct 346 ms 13552 KB Output is correct
5 Correct 253 ms 12880 KB Output is correct
6 Incorrect 207 ms 13048 KB Output isn't correct
7 Correct 243 ms 11472 KB Output is correct
8 Correct 119 ms 17232 KB Output is correct
9 Correct 109 ms 9348 KB Output is correct