oj.uz

Submission #792762

# Submission time Handle Problem Language Result Execution time Memory
792762 2023-07-25T08:33:24 Z t6twotwo Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 530 ms 39928 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int &x : A) {
        cin >> x;
    }
    vector<int> queries(Q), ans(Q);
    vector<vector<int>> q(N + 1);
    for (int i = 0; i < Q; i++) {
        int t, p;
        cin >> t >> p;
        t = min(t, N);
        p--;
        queries[i] = p;
        if (t == 0) {
            ans[i] = A[p];
        } else {
            q[t].push_back(i);
        }
    }
    vector<int> f(N, N), stk;
    for (int i = N - 1; i >= 0; i--) {
        while (!stk.empty() && A[stk.back()] < A[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            f[i] = stk.back();
        }
        stk.push_back(i);
    }
    vector<int> bit(N + 1);
    auto add = [&](int p, int x) {
        for (int i = p; i <= N; i += i & -i) {
            bit[i] += x;
        }
    };
    auto sum = [&](int p) {
        int s = 0;
        for (int i = p; i; i -= i & -i) {
            s += bit[i];
        }
        return s;
    };
    vector<int> L(N + 1), R(N + 1);
    set<tuple<int, int, int>> s, t;
    for (int i = 0; i < N; i = f[i]) {
        L[A[i]] = i;
        R[A[i]] = f[i];
        s.emplace(A[i], L[A[i]], R[A[i]]);
        add(A[i], R[A[i]] - L[A[i]]);
    }
    int T = N;
    for (int i = 1; i <= N; i++) {
        if (T > N / 2) {
            while (1) {
                auto [_, l, r] = *prev(s.end());
                if (T - r + l < N / 2) {
                    break;
                }
                T -= r - l;
                s.erase(prev(s.end()));
            }
            if (T > N / 2) {
                auto [v, l, r] = *prev(s.end());
                s.erase(prev(s.end()));
                int m = r - T + N / 2;
                s.emplace(v, l, m);
                add(v, m - r);
                R[v] = m;
                for (int i = m; i < r; i = f[i]) {
                    L[A[i]] = i;
                    R[A[i]] = min(r, f[i]);
                    s.emplace(A[i], L[A[i]], R[A[i]]);
                    add(A[i], R[A[i]] - L[A[i]]);
                }
            }
        }
        for (int k : q[i]) {
            int p = queries[k] + 1;
            int pos = 0, sum0 = 0;
            for (int i = 17; i >= 0; i--) {
                if (pos + (1 << i) <= N && bit[pos + (1 << i)] + sum0 < p) {
                    pos += 1 << i;
                    sum0 += bit[pos];
                }
            }
            pos++;
            ans[k] = A[R[pos] - sum(pos) + p - 1];
        }
    }
    for (int x : ans) {
        cout << x << "\n";
    }
    return 6/22;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 17396 KB Output is correct
2 Correct 232 ms 16472 KB Output is correct
3 Correct 217 ms 16052 KB Output is correct
4 Correct 203 ms 16208 KB Output is correct
5 Correct 239 ms 17724 KB Output is correct
6 Correct 205 ms 17524 KB Output is correct
7 Correct 228 ms 18068 KB Output is correct
8 Correct 188 ms 16784 KB Output is correct
9 Correct 196 ms 16940 KB Output is correct
10 Correct 190 ms 16020 KB Output is correct
11 Correct 230 ms 16012 KB Output is correct
12 Correct 177 ms 14516 KB Output is correct
13 Correct 251 ms 15960 KB Output is correct
14 Correct 209 ms 17084 KB Output is correct
15 Correct 205 ms 16736 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 150 ms 11780 KB Output is correct
18 Correct 167 ms 13512 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 33428 KB Output is correct
2 Correct 346 ms 37068 KB Output is correct
3 Correct 263 ms 29256 KB Output is correct
4 Correct 233 ms 26012 KB Output is correct
5 Correct 245 ms 26848 KB Output is correct
6 Correct 224 ms 25760 KB Output is correct
7 Correct 264 ms 28572 KB Output is correct
8 Correct 296 ms 28252 KB Output is correct
9 Correct 243 ms 26016 KB Output is correct
10 Correct 262 ms 26292 KB Output is correct
11 Correct 200 ms 23368 KB Output is correct
12 Correct 219 ms 23172 KB Output is correct
13 Correct 290 ms 26200 KB Output is correct
14 Correct 208 ms 23564 KB Output is correct
15 Correct 254 ms 26720 KB Output is correct
16 Correct 18 ms 8908 KB Output is correct
17 Correct 236 ms 35116 KB Output is correct
18 Correct 189 ms 22580 KB Output is correct
19 Correct 51 ms 11652 KB Output is correct
20 Correct 71 ms 12232 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 11104 KB Output is correct
2 Correct 69 ms 11960 KB Output is correct
3 Correct 67 ms 10316 KB Output is correct
4 Correct 41 ms 7220 KB Output is correct
5 Correct 68 ms 10084 KB Output is correct
6 Correct 56 ms 7428 KB Output is correct
7 Correct 52 ms 8940 KB Output is correct
8 Correct 47 ms 8072 KB Output is correct
9 Correct 50 ms 9164 KB Output is correct
10 Correct 35 ms 6460 KB Output is correct
11 Correct 46 ms 6856 KB Output is correct
12 Correct 43 ms 6396 KB Output is correct
13 Correct 35 ms 6528 KB Output is correct
14 Correct 33 ms 6580 KB Output is correct
15 Correct 32 ms 6452 KB Output is correct
16 Correct 14 ms 4700 KB Output is correct
17 Correct 41 ms 12168 KB Output is correct
18 Correct 27 ms 6040 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 17396 KB Output is correct
2 Correct 232 ms 16472 KB Output is correct
3 Correct 217 ms 16052 KB Output is correct
4 Correct 203 ms 16208 KB Output is correct
5 Correct 239 ms 17724 KB Output is correct
6 Correct 205 ms 17524 KB Output is correct
7 Correct 228 ms 18068 KB Output is correct
8 Correct 188 ms 16784 KB Output is correct
9 Correct 196 ms 16940 KB Output is correct
10 Correct 190 ms 16020 KB Output is correct
11 Correct 230 ms 16012 KB Output is correct
12 Correct 177 ms 14516 KB Output is correct
13 Correct 251 ms 15960 KB Output is correct
14 Correct 209 ms 17084 KB Output is correct
15 Correct 205 ms 16736 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 150 ms 11780 KB Output is correct
18 Correct 167 ms 13512 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 339 ms 33428 KB Output is correct
22 Correct 346 ms 37068 KB Output is correct
23 Correct 263 ms 29256 KB Output is correct
24 Correct 233 ms 26012 KB Output is correct
25 Correct 245 ms 26848 KB Output is correct
26 Correct 224 ms 25760 KB Output is correct
27 Correct 264 ms 28572 KB Output is correct
28 Correct 296 ms 28252 KB Output is correct
29 Correct 243 ms 26016 KB Output is correct
30 Correct 262 ms 26292 KB Output is correct
31 Correct 200 ms 23368 KB Output is correct
32 Correct 219 ms 23172 KB Output is correct
33 Correct 290 ms 26200 KB Output is correct
34 Correct 208 ms 23564 KB Output is correct
35 Correct 254 ms 26720 KB Output is correct
36 Correct 18 ms 8908 KB Output is correct
37 Correct 236 ms 35116 KB Output is correct
38 Correct 189 ms 22580 KB Output is correct
39 Correct 51 ms 11652 KB Output is correct
40 Correct 71 ms 12232 KB Output is correct
41 Correct 66 ms 11104 KB Output is correct
42 Correct 69 ms 11960 KB Output is correct
43 Correct 67 ms 10316 KB Output is correct
44 Correct 41 ms 7220 KB Output is correct
45 Correct 68 ms 10084 KB Output is correct
46 Correct 56 ms 7428 KB Output is correct
47 Correct 52 ms 8940 KB Output is correct
48 Correct 47 ms 8072 KB Output is correct
49 Correct 50 ms 9164 KB Output is correct
50 Correct 35 ms 6460 KB Output is correct
51 Correct 46 ms 6856 KB Output is correct
52 Correct 43 ms 6396 KB Output is correct
53 Correct 35 ms 6528 KB Output is correct
54 Correct 33 ms 6580 KB Output is correct
55 Correct 32 ms 6452 KB Output is correct
56 Correct 14 ms 4700 KB Output is correct
57 Correct 41 ms 12168 KB Output is correct
58 Correct 27 ms 6040 KB Output is correct
59 Correct 1 ms 212 KB Output is correct
60 Correct 1 ms 212 KB Output is correct
61 Correct 530 ms 39128 KB Output is correct
62 Correct 526 ms 39928 KB Output is correct
63 Correct 498 ms 36300 KB Output is correct
64 Correct 430 ms 31988 KB Output is correct
65 Correct 414 ms 33424 KB Output is correct
66 Correct 379 ms 31856 KB Output is correct
67 Correct 329 ms 30284 KB Output is correct
68 Correct 401 ms 29912 KB Output is correct
69 Correct 363 ms 31496 KB Output is correct
70 Correct 306 ms 27584 KB Output is correct
71 Correct 256 ms 29260 KB Output is correct
72 Correct 313 ms 27604 KB Output is correct
73 Correct 287 ms 28124 KB Output is correct
74 Correct 308 ms 29152 KB Output is correct
75 Correct 326 ms 28624 KB Output is correct
76 Correct 19 ms 8916 KB Output is correct
77 Correct 227 ms 35136 KB Output is correct
78 Correct 216 ms 24256 KB Output is correct
79 Correct 0 ms 212 KB Output is correct
80 Correct 0 ms 212 KB Output is correct