oj.uz

Submission #872112

# Submission time Handle Problem Language Result Execution time Memory
872112 2023-11-12T10:25:28 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 450 ms 25776 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 200000

int root, n, q, L[N], J[N], P[N], tout[N], rv[N], timer, t[N<<1], low[N];
int 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 4 ms 13916 KB Output is correct
2 Correct 99 ms 17088 KB Output is correct
3 Correct 86 ms 17660 KB Output is correct
4 Incorrect 4 ms 13912 KB Output isn't correct
5 Correct 4 ms 13912 KB Output is correct
6 Correct 4 ms 13916 KB Output is correct
7 Incorrect 5 ms 13916 KB Output isn't correct
8 Correct 5 ms 13916 KB Output is correct
9 Correct 9 ms 14100 KB Output is correct
10 Correct 22 ms 14428 KB Output is correct
11 Correct 96 ms 17236 KB Output is correct
12 Correct 85 ms 17488 KB Output is correct
13 Incorrect 101 ms 17232 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 18020 KB Output is correct
2 Correct 91 ms 21332 KB Output is correct
3 Correct 120 ms 17608 KB Output is correct
4 Correct 55 ms 17752 KB Output is correct
5 Correct 57 ms 17628 KB Output is correct
6 Incorrect 54 ms 17500 KB Output isn't correct
7 Correct 55 ms 17128 KB Output is correct
8 Correct 68 ms 18004 KB Output is correct
9 Correct 91 ms 21588 KB Output is correct
10 Correct 93 ms 21328 KB Output is correct
11 Incorrect 84 ms 21264 KB Output isn't correct
12 Correct 88 ms 19540 KB Output is correct
13 Correct 133 ms 24800 KB Output is correct
14 Correct 111 ms 17524 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 18848 KB Output is correct
2 Correct 250 ms 19792 KB Output is correct
3 Correct 257 ms 23892 KB Output is correct
4 Correct 186 ms 20488 KB Output is correct
5 Correct 156 ms 20120 KB Output is correct
6 Correct 153 ms 20436 KB Output is correct
7 Correct 148 ms 19012 KB Output is correct
8 Correct 255 ms 23892 KB Output is correct
9 Correct 265 ms 21844 KB Output is correct
10 Correct 259 ms 21384 KB Output is correct
11 Correct 271 ms 21584 KB Output is correct
12 Correct 252 ms 19936 KB Output is correct
13 Correct 450 ms 25776 KB Output is correct
14 Correct 88 ms 17476 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 22016 KB Output is correct
2 Correct 246 ms 19884 KB Output is correct
3 Correct 123 ms 25708 KB Output is correct
4 Correct 355 ms 22368 KB Output is correct
5 Correct 253 ms 21336 KB Output is correct
6 Incorrect 198 ms 21332 KB Output isn't correct
7 Correct 261 ms 19824 KB Output is correct
8 Correct 121 ms 25684 KB Output is correct
9 Correct 104 ms 17616 KB Output is correct