oj.uz

Submission #872098

# Submission time Handle Problem Language Result Execution time Memory
872098 2023-11-12T10:03:30 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
80.1465 / 100
 452 ms 18060 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 200000

int root, n, q, L[N], J[N], P[N], ne, 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);
}

inline 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;
}

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;

    //for (int i = 0; i < ne; ++i) cerr <<"Edge("<<g[i].first<<" > " << g[i].second<<")"<<endl;

    P[root] = root; J[root] = root;
    dfs(root);

    //for (int i = 0; i < n; ++i) cerr << "Node("<<i<<") Time("<<tin[i]<<") Low("<<low[i]<<") " <<" Head(" <<h[i]<<")"<<endl;

    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
15.3846153846 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9564 KB Output is correct
2 Correct 103 ms 10656 KB Output is correct
3 Incorrect 87 ms 10368 KB Output isn't correct
4 Incorrect 3 ms 9564 KB Output isn't correct
5 Correct 3 ms 9560 KB Output is correct
6 Correct 5 ms 9564 KB Output is correct
7 Incorrect 4 ms 9564 KB Output isn't correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 8 ms 9820 KB Output is correct
10 Correct 22 ms 10092 KB Output is correct
11 Correct 137 ms 10876 KB Output is correct
12 Incorrect 82 ms 10324 KB Output isn't correct
13 Incorrect 115 ms 10240 KB Output isn't correct

Subtask #2
21.4285714286 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10212 KB Output is correct
2 Incorrect 210 ms 13392 KB Output isn't correct
3 Correct 120 ms 10156 KB Output is correct
4 Correct 55 ms 11352 KB Output is correct
5 Correct 57 ms 11356 KB Output is correct
6 Incorrect 57 ms 11344 KB Output isn't correct
7 Correct 59 ms 10828 KB Output is correct
8 Correct 71 ms 10228 KB Output is correct
9 Correct 96 ms 10736 KB Output is correct
10 Incorrect 220 ms 13536 KB Output isn't correct
11 Incorrect 89 ms 14148 KB Output isn't correct
12 Correct 90 ms 12368 KB Output is correct
13 Correct 123 ms 15444 KB Output is correct
14 Correct 119 ms 10076 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 11048 KB Output is correct
2 Correct 275 ms 13176 KB Output is correct
3 Correct 253 ms 15504 KB Output is correct
4 Correct 194 ms 13728 KB Output is correct
5 Correct 155 ms 13660 KB Output is correct
6 Correct 156 ms 13908 KB Output is correct
7 Correct 151 ms 12120 KB Output is correct
8 Correct 259 ms 15492 KB Output is correct
9 Correct 262 ms 15132 KB Output is correct
10 Correct 264 ms 15004 KB Output is correct
11 Correct 273 ms 14420 KB Output is correct
12 Correct 257 ms 13052 KB Output is correct
13 Correct 452 ms 18060 KB Output is correct
14 Correct 92 ms 10880 KB Output is correct

Subtask #4
3.33333333333 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 14928 KB Output is correct
2 Incorrect 239 ms 12884 KB Output isn't correct
3 Correct 108 ms 13392 KB Output is correct
4 Correct 362 ms 14820 KB Output is correct
5 Correct 254 ms 14796 KB Output is correct
6 Incorrect 203 ms 11604 KB Output isn't correct
7 Incorrect 252 ms 12908 KB Output isn't correct
8 Correct 115 ms 13572 KB Output is correct
9 Correct 112 ms 10308 KB Output is correct