oj.uz

Submission #872093

# Submission time Handle Problem Language Result Execution time Memory
872093 2023-11-12T09:57:34 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
17.4359 / 100
 370 ms 15028 KB 
#include <iostream>
#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], ne, ta[N], h[N], tin[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);
}

int qry(int u) { return qry(tin[u], tin[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[tin[u] = timer++] = u;
}

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 < n; ++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(tin[r], tin[r], 0);
            cout << L[k-1] - L[r] << '\n';
        }
    }

    return 0;
}

Subtask #1
5.76923076923 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5976 KB Output isn't correct
2 Incorrect 97 ms 7708 KB Output isn't correct
3 Incorrect 84 ms 7964 KB Output isn't correct
4 Incorrect 2 ms 5976 KB Output isn't correct
5 Incorrect 2 ms 5984 KB Output isn't correct
6 Incorrect 2 ms 5980 KB Output isn't correct
7 Incorrect 3 ms 5980 KB Output isn't correct
8 Correct 2 ms 5980 KB Output is correct
9 Correct 7 ms 6236 KB Output is correct
10 Correct 19 ms 6580 KB Output is correct
11 Incorrect 104 ms 7832 KB Output isn't correct
12 Incorrect 81 ms 7736 KB Output isn't correct
13 Incorrect 102 ms 7856 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 7248 KB Output isn't correct
2 Incorrect 266 ms 10956 KB Output isn't correct
3 Correct 115 ms 8032 KB Output is correct
4 Incorrect 69 ms 8360 KB Output isn't correct
5 Incorrect 65 ms 8276 KB Output isn't correct
6 Incorrect 54 ms 8280 KB Output isn't correct
7 Incorrect 58 ms 7792 KB Output isn't correct
8 Incorrect 66 ms 7116 KB Output isn't correct
9 Incorrect 99 ms 8600 KB Output isn't correct
10 Incorrect 262 ms 11004 KB Output isn't correct
11 Incorrect 87 ms 12112 KB Output isn't correct
12 Incorrect 94 ms 10128 KB Output isn't correct
13 Incorrect 131 ms 13416 KB Output isn't correct
14 Correct 113 ms 7764 KB Output is correct

Subtask #3
5.71428571429 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 7516 KB Output isn't correct
2 Incorrect 187 ms 10324 KB Output isn't correct
3 Incorrect 258 ms 12788 KB Output isn't correct
4 Incorrect 184 ms 10932 KB Output isn't correct
5 Incorrect 194 ms 10732 KB Output isn't correct
6 Correct 164 ms 11092 KB Output is correct
7 Incorrect 126 ms 9264 KB Output isn't correct
8 Incorrect 249 ms 12384 KB Output isn't correct
9 Incorrect 266 ms 12624 KB Output isn't correct
10 Correct 270 ms 12244 KB Output is correct
11 Incorrect 274 ms 11912 KB Output isn't correct
12 Incorrect 189 ms 10272 KB Output isn't correct
13 Incorrect 370 ms 15028 KB Output isn't correct
14 Incorrect 97 ms 8528 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 12500 KB Output is correct
2 Incorrect 198 ms 10436 KB Output isn't correct
3 Incorrect 110 ms 10836 KB Output isn't correct
4 Correct 344 ms 12692 KB Output is correct
5 Incorrect 253 ms 12372 KB Output isn't correct
6 Incorrect 243 ms 9552 KB Output isn't correct
7 Incorrect 195 ms 10324 KB Output isn't correct
8 Incorrect 107 ms 10356 KB Output isn't correct
9 Correct 105 ms 7968 KB Output is correct