oj.uz

답안 #872100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872100 2023-11-12T10:06:45 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
89.3895 / 100
 439 ms 19180 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 < ne; ++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);
            update(tout[r], tout[r], 0);
            cout << L[k-1] - L[r] << '\n';
        }
    }

    return 0;
}

Subtask #1
19.2307692308 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9564 KB Output is correct
2 Correct 99 ms 10520 KB Output is correct
3 Correct 81 ms 10332 KB Output is 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 3 ms 9564 KB Output isn't correct
8 Correct 4 ms 9564 KB Output is correct
9 Correct 8 ms 9820 KB Output is correct
10 Correct 22 ms 10076 KB Output is correct
11 Correct 102 ms 11048 KB Output is correct
12 Correct 81 ms 10320 KB Output is correct
13 Incorrect 103 ms 10184 KB Output isn't correct

Subtask #2
25.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 11532 KB Output is correct
2 Correct 100 ms 14672 KB Output is correct
3 Correct 115 ms 10156 KB Output is correct
4 Correct 55 ms 11444 KB Output is correct
5 Correct 68 ms 11504 KB Output is correct
6 Incorrect 56 ms 11280 KB Output isn't correct
7 Correct 57 ms 10836 KB Output is correct
8 Correct 86 ms 11452 KB Output is correct
9 Correct 94 ms 14604 KB Output is correct
10 Correct 94 ms 14676 KB Output is correct
11 Incorrect 96 ms 14712 KB Output isn't correct
12 Correct 106 ms 12372 KB Output is correct
13 Correct 124 ms 17236 KB Output is correct
14 Correct 115 ms 10204 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 12636 KB Output is correct
2 Correct 266 ms 13180 KB Output is correct
3 Correct 262 ms 16976 KB Output is correct
4 Correct 200 ms 13904 KB Output is correct
5 Correct 158 ms 13660 KB Output is correct
6 Correct 154 ms 13808 KB Output is correct
7 Correct 156 ms 12208 KB Output is correct
8 Correct 255 ms 16980 KB Output is correct
9 Correct 277 ms 15164 KB Output is correct
10 Correct 266 ms 14928 KB Output is correct
11 Correct 265 ms 15076 KB Output is correct
12 Correct 264 ms 13028 KB Output is correct
13 Correct 439 ms 19180 KB Output is correct
14 Correct 111 ms 10952 KB Output is correct

Subtask #4
4.44444444444 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 354 ms 14748 KB Output is correct
2 Correct 255 ms 13136 KB Output is correct
3 Correct 119 ms 18248 KB Output is correct
4 Correct 350 ms 14912 KB Output is correct
5 Correct 290 ms 14752 KB Output is correct
6 Incorrect 200 ms 14160 KB Output isn't correct
7 Correct 246 ms 12884 KB Output is correct
8 Correct 136 ms 18112 KB Output is correct
9 Correct 106 ms 10232 KB Output is correct