oj.uz

Submission #872120

# Submission time Handle Problem Language Result Execution time Memory
872120 2023-11-12T10:41:06 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 445 ms 19156 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);
}

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];
}

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

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;
}

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));

    function<void(int)> dfs0 = [&](int u)
    {
        low[u] = u;
        for (auto v : g[u]) dfs0(v), low[u] = min(low[u], low[v]);
    };
    dfs0(root);

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

    dfs(P[root] = J[root] = root);
    assert(timer == n);

    memset(lz, -1, sizeof lz);
}

void answer()
{
    for (int l, r, t, k; q--;)
    {
        cin >> t >> k;
        if (t == 1)
        {
            for (l = 0, r = n - 1; 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
        {
            r = highest(k-1);
            update(tout[r], tout[r], 0);
            cout << L[k-1] - L[r] << '\n';
        }
    }
}

int main()
{
    init();
    answer();

    return 0;
}

Subtask #1
19.2307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 91 ms 6700 KB Output is correct
3 Correct 84 ms 7252 KB Output is correct
4 Incorrect 1 ms 4700 KB Output isn't correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4852 KB Output is correct
7 Incorrect 2 ms 4700 KB Output isn't correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 6 ms 4884 KB Output is correct
10 Correct 17 ms 5212 KB Output is correct
11 Correct 91 ms 6764 KB Output is correct
12 Correct 87 ms 6864 KB Output is correct
13 Incorrect 115 ms 6704 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 7508 KB Output is correct
2 Correct 84 ms 12932 KB Output is correct
3 Correct 116 ms 7628 KB Output is correct
4 Correct 55 ms 7188 KB Output is correct
5 Correct 51 ms 7000 KB Output is correct
6 Incorrect 49 ms 7000 KB Output isn't correct
7 Correct 50 ms 6236 KB Output is correct
8 Correct 65 ms 7260 KB Output is correct
9 Correct 101 ms 13392 KB Output is correct
10 Correct 81 ms 12880 KB Output is correct
11 Incorrect 80 ms 12880 KB Output isn't correct
12 Correct 84 ms 10320 KB Output is correct
13 Correct 114 ms 17236 KB Output is correct
14 Correct 107 ms 7624 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 8940 KB Output is correct
2 Correct 252 ms 10768 KB Output is correct
3 Correct 269 ms 16088 KB Output is correct
4 Correct 179 ms 11520 KB Output is correct
5 Correct 156 ms 11344 KB Output is correct
6 Correct 149 ms 11336 KB Output is correct
7 Correct 142 ms 9300 KB Output is correct
8 Correct 250 ms 16020 KB Output is correct
9 Correct 276 ms 13408 KB Output is correct
10 Correct 255 ms 13044 KB Output is correct
11 Correct 294 ms 13012 KB Output is correct
12 Correct 247 ms 10644 KB Output is correct
13 Correct 445 ms 19156 KB Output is correct
14 Correct 87 ms 7632 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 13796 KB Output is correct
2 Correct 236 ms 10716 KB Output is correct
3 Correct 115 ms 18936 KB Output is correct
4 Correct 359 ms 13576 KB Output is correct
5 Correct 287 ms 13036 KB Output is correct
6 Incorrect 189 ms 13008 KB Output isn't correct
7 Correct 247 ms 10632 KB Output is correct
8 Correct 121 ms 19012 KB Output is correct
9 Correct 100 ms 7536 KB Output is correct