oj.uz

Submission #872099

# Submission time Handle Problem Language Result Execution time Memory
872099 2023-11-12T10:06:17 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
80.1465 / 100
 454 ms 18004 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], ne, h[N], tout[N], rv[N], timer, t[N<<1], low[N];
char lz[N];
pair<int, 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;
    int m = (l+r)/2, vl =v + 1, vr=v+(m-l+1)*2;
    if (x <= l && r <= y) {lz[v] = k; push(v, l, r); return; }
    update(x, y, k, vl, l, m), update(x, y, k, vr, m+1, r);
    t[v] = t[vl]+t[vr];
}

void init()
{
    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 j = h[u]; j < ne && g[j].first == u; ++j)
            dfs(g[j].second);
        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]);
}

void dfs(int u)
{
    for (auto j = h[u]; j < ne && g[j].first == u; ++j)
    {
        P[g[j].second] = u;
        if (L[u] - L[J[u]] == L[J[u]] - L[J[J[u]]]) J[g[j].second] = J[J[u]];
        else J[g[j].second] = u;
        L[g[j].second] = L[u] + 1;
        dfs(g[j].second);
    }
    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()
{
    ShinLena;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> P[i], (P[i] ? void(g[ne++] = {P[i]-1, i}) : void(root = i));
    sort(g, g+ne);
    for (int i = 0; i < n; ++i) if (!i || g[i].first != g[i-1].first) h[g[i].first] = i;

    init();

    sort(g, g+ne, [](const auto &a, const auto &b){
            if (a.first != b.first) return a.first < b.first;
            return low[a.second] < low[b.second];
    });

    for (int i = 0; i < ne; ++i) if (!i || g[i].first != g[i-1].first) h[g[i].first] = i;

    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;
            }
            cout << rv[l-1] + 1 << '\n';
            update(0, l-1, 1);
        }
        else
        {
            int r = highest(k-1);
            if (P[r] != r) assert(!qry(P[r]));
            update(tout[r], tout[r], 0);
            cout << L[k-1] - L[r] << '\n';
        }
    }

    return 0;
}

Subtask #1
15.3846153846 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9560 KB Output is correct
2 Correct 112 ms 10536 KB Output is correct
3 Incorrect 84 ms 10324 KB Output isn't correct
4 Incorrect 3 ms 9560 KB Output isn't correct
5 Correct 3 ms 9564 KB Output is correct
6 Correct 3 ms 9564 KB Output is correct
7 Incorrect 4 ms 9744 KB Output isn't correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 13 ms 9820 KB Output is correct
10 Correct 23 ms 10072 KB Output is correct
11 Correct 111 ms 10580 KB Output is correct
12 Incorrect 90 ms 10372 KB Output isn't correct
13 Incorrect 122 ms 10324 KB Output isn't correct

Subtask #2
21.4285714286 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 10252 KB Output is correct
2 Incorrect 222 ms 13228 KB Output isn't correct
3 Correct 120 ms 10068 KB Output is correct
4 Correct 63 ms 11396 KB Output is correct
5 Correct 67 ms 11564 KB Output is correct
6 Incorrect 64 ms 11348 KB Output isn't correct
7 Correct 65 ms 10832 KB Output is correct
8 Correct 70 ms 10316 KB Output is correct
9 Correct 89 ms 10580 KB Output is correct
10 Incorrect 221 ms 13240 KB Output isn't correct
11 Incorrect 99 ms 14152 KB Output isn't correct
12 Correct 104 ms 12368 KB Output is correct
13 Correct 124 ms 15440 KB Output is correct
14 Correct 122 ms 10172 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 11032 KB Output is correct
2 Correct 272 ms 13132 KB Output is correct
3 Correct 265 ms 15636 KB Output is correct
4 Correct 197 ms 13804 KB Output is correct
5 Correct 164 ms 13708 KB Output is correct
6 Correct 163 ms 13660 KB Output is correct
7 Correct 156 ms 12120 KB Output is correct
8 Correct 260 ms 15444 KB Output is correct
9 Correct 283 ms 15484 KB Output is correct
10 Correct 277 ms 14932 KB Output is correct
11 Correct 273 ms 14472 KB Output is correct
12 Correct 264 ms 13108 KB Output is correct
13 Correct 454 ms 18004 KB Output is correct
14 Correct 102 ms 11092 KB Output is correct

Subtask #4
3.33333333333 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 14804 KB Output is correct
2 Incorrect 257 ms 13148 KB Output isn't correct
3 Correct 113 ms 13584 KB Output is correct
4 Correct 366 ms 14932 KB Output is correct
5 Correct 270 ms 14588 KB Output is correct
6 Incorrect 204 ms 11508 KB Output isn't correct
7 Incorrect 253 ms 12896 KB Output isn't correct
8 Correct 114 ms 13488 KB Output is correct
9 Correct 112 ms 10292 KB Output is correct