oj.uz

Submission #872118

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

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

    for (int i = 0; i < n; ++i) sort(ALL(g[i]), [](int a, int b){ if(low[a]-low[b])return low[a]<low[b]; return a<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;
            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 1 ms 4700 KB Output is correct
2 Correct 93 ms 6688 KB Output is correct
3 Correct 74 ms 6788 KB Output is correct
4 Incorrect 1 ms 4696 KB Output isn't correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Incorrect 2 ms 4700 KB Output isn't correct
8 Correct 2 ms 4784 KB Output is correct
9 Correct 6 ms 4700 KB Output is correct
10 Correct 18 ms 5196 KB Output is correct
11 Correct 92 ms 6636 KB Output is correct
12 Correct 75 ms 6992 KB Output is correct
13 Incorrect 98 ms 6736 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 7400 KB Output is correct
2 Correct 90 ms 12880 KB Output is correct
3 Correct 106 ms 7628 KB Output is correct
4 Correct 50 ms 7260 KB Output is correct
5 Correct 52 ms 7000 KB Output is correct
6 Incorrect 50 ms 7176 KB Output isn't correct
7 Correct 50 ms 6236 KB Output is correct
8 Correct 66 ms 7508 KB Output is correct
9 Correct 76 ms 13144 KB Output is correct
10 Correct 82 ms 12880 KB Output is correct
11 Incorrect 78 ms 12884 KB Output isn't correct
12 Correct 79 ms 10400 KB Output is correct
13 Correct 114 ms 17236 KB Output is correct
14 Correct 108 ms 7632 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 9040 KB Output is correct
2 Correct 250 ms 10608 KB Output is correct
3 Correct 247 ms 16132 KB Output is correct
4 Correct 179 ms 11516 KB Output is correct
5 Correct 147 ms 11492 KB Output is correct
6 Correct 147 ms 11188 KB Output is correct
7 Correct 141 ms 9376 KB Output is correct
8 Correct 249 ms 15952 KB Output is correct
9 Correct 253 ms 13488 KB Output is correct
10 Correct 259 ms 13104 KB Output is correct
11 Correct 250 ms 13116 KB Output is correct
12 Correct 246 ms 10760 KB Output is correct
13 Correct 445 ms 19136 KB Output is correct
14 Correct 83 ms 7664 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 13648 KB Output is correct
2 Correct 239 ms 10688 KB Output is correct
3 Correct 111 ms 18780 KB Output is correct
4 Correct 350 ms 13544 KB Output is correct
5 Correct 251 ms 13096 KB Output is correct
6 Incorrect 190 ms 12880 KB Output isn't correct
7 Correct 242 ms 10580 KB Output is correct
8 Correct 111 ms 18944 KB Output is correct
9 Correct 97 ms 7628 KB Output is correct