oj.uz

Submission #872113

# Submission time Handle Problem Language Result Execution time Memory
872113 2023-11-12T10:30:24 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 443 ms 17596 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];
signed 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();
    dfs(P[root] = J[root] = root);

    memset(lz, -1, sizeof lz);
    for (int t, k; q--;)
    {
        cin >> t >> k;
        if (t == 1)
        {
            int l = 0, r = n - 1, z = -1;
            while (l <= r)
            {
                int m = (l+r)/2;
                if (m + 1 - qry(0, m) <= k) l = m + 1, z = m;
                else r = m - 1;
            }
            assert(z+1);
            update(0, z, 1);
            cout << rv[z] + 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 6236 KB Output is correct
2 Correct 101 ms 8448 KB Output is correct
3 Correct 79 ms 8464 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 3 ms 6236 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 6432 KB Output is correct
10 Correct 20 ms 6760 KB Output is correct
11 Correct 93 ms 8276 KB Output is correct
12 Correct 86 ms 8560 KB Output is correct
13 Incorrect 100 ms 8236 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8280 KB Output is correct
2 Correct 89 ms 12880 KB Output is correct
3 Correct 116 ms 9152 KB Output is correct
4 Correct 53 ms 8284 KB Output is correct
5 Correct 54 ms 8216 KB Output is correct
6 Incorrect 52 ms 8260 KB Output isn't correct
7 Correct 52 ms 7664 KB Output is correct
8 Correct 68 ms 8336 KB Output is correct
9 Correct 86 ms 13380 KB Output is correct
10 Correct 90 ms 12852 KB Output is correct
11 Incorrect 85 ms 12884 KB Output isn't correct
12 Correct 90 ms 11600 KB Output is correct
13 Correct 130 ms 15988 KB Output is correct
14 Correct 107 ms 9144 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 9692 KB Output is correct
2 Correct 257 ms 11404 KB Output is correct
3 Correct 255 ms 15180 KB Output is correct
4 Correct 183 ms 11860 KB Output is correct
5 Correct 151 ms 11544 KB Output is correct
6 Correct 161 ms 11604 KB Output is correct
7 Correct 146 ms 10324 KB Output is correct
8 Correct 279 ms 15188 KB Output is correct
9 Correct 259 ms 13456 KB Output is correct
10 Correct 300 ms 13156 KB Output is correct
11 Correct 255 ms 13108 KB Output is correct
12 Correct 244 ms 11348 KB Output is correct
13 Correct 443 ms 17596 KB Output is correct
14 Correct 88 ms 9164 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 13944 KB Output is correct
2 Correct 241 ms 11344 KB Output is correct
3 Correct 121 ms 17376 KB Output is correct
4 Correct 369 ms 13516 KB Output is correct
5 Correct 252 ms 12884 KB Output is correct
6 Incorrect 201 ms 13408 KB Output isn't correct
7 Correct 241 ms 11344 KB Output is correct
8 Correct 117 ms 17364 KB Output is correct
9 Correct 105 ms 9316 KB Output is correct