oj.uz

Submission #872114

# Submission time Handle Problem Language Result Execution time Memory
872114 2023-11-12T10:33:14 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 459 ms 19024 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){ 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;
            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 91 ms 6724 KB Output is correct
3 Correct 75 ms 6864 KB Output is correct
4 Incorrect 1 ms 4696 KB Output isn't correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Incorrect 3 ms 4700 KB Output isn't correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 6 ms 4700 KB Output is correct
10 Correct 24 ms 5224 KB Output is correct
11 Correct 98 ms 6816 KB Output is correct
12 Correct 76 ms 6820 KB Output is correct
13 Incorrect 97 ms 6784 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 7300 KB Output is correct
2 Correct 88 ms 12776 KB Output is correct
3 Correct 115 ms 7552 KB Output is correct
4 Correct 50 ms 7260 KB Output is correct
5 Correct 52 ms 7000 KB Output is correct
6 Incorrect 51 ms 7188 KB Output isn't correct
7 Correct 53 ms 6236 KB Output is correct
8 Correct 70 ms 7504 KB Output is correct
9 Correct 76 ms 13216 KB Output is correct
10 Correct 86 ms 12888 KB Output is correct
11 Incorrect 77 ms 12904 KB Output isn't correct
12 Correct 85 ms 10324 KB Output is correct
13 Correct 125 ms 17200 KB Output is correct
14 Correct 115 ms 7588 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 9044 KB Output is correct
2 Correct 258 ms 10576 KB Output is correct
3 Correct 255 ms 15956 KB Output is correct
4 Correct 187 ms 11668 KB Output is correct
5 Correct 147 ms 11160 KB Output is correct
6 Correct 147 ms 11344 KB Output is correct
7 Correct 145 ms 9300 KB Output is correct
8 Correct 271 ms 15976 KB Output is correct
9 Correct 260 ms 13628 KB Output is correct
10 Correct 271 ms 13144 KB Output is correct
11 Correct 253 ms 13064 KB Output is correct
12 Correct 241 ms 10696 KB Output is correct
13 Correct 459 ms 19024 KB Output is correct
14 Correct 87 ms 7628 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 13788 KB Output is correct
2 Correct 236 ms 10640 KB Output is correct
3 Correct 121 ms 18888 KB Output is correct
4 Correct 345 ms 13460 KB Output is correct
5 Correct 254 ms 13120 KB Output is correct
6 Incorrect 198 ms 13288 KB Output isn't correct
7 Correct 242 ms 10752 KB Output is correct
8 Correct 123 ms 18808 KB Output is correct
9 Correct 106 ms 7632 KB Output is correct