oj.uz

Submission #656854

# Submission time Handle Problem Language Result Execution time Memory
656854 2022-11-08T11:24:16 Z dooompy Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 900 ms 100344 KB 
#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

int a[2000005];
int ans[2000005];

struct info {
    int val, l, r;
    bool operator<(info o) const {
        if (val == o.val) return l < o.l;
        return val < o.val;
    }
};

set<array<int, 3>> st;

int tree[4 * 2000005];

void update(int x, int l, int r, int p, int v) {
    if (l == r) {
        tree[x] += v;
        return;
    }

    int mid = (l + r) / 2;
    if (p <= mid) update(2 * x, l, mid, p, v);
    else update(2 * x + 1, mid + 1, r, p, v);

    tree[x] = tree[2 * x] + tree[2 * x + 1];
}

int walk(int x, int l, int r, int v) {
    if (l == r) return l;

    int mid = (l + r) / 2;

    if (tree[2 * x] >= v) return walk(2 * x, l, mid, v);
    else return walk(2 *x + 1, mid + 1, r, v-  tree[2 * x]);
}

int sum(int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[x];
    if (l > qr || ql > r) return 0;

    int mid = (l + r) / 2;

    return sum(2 * x, l, mid, ql, qr) + sum(2 * x + 1, mid + 1, r, ql, qr);
}

void add(int val, int l, int r) {
    st.insert({val, l, r});
    update(1, 1, 200000, val, r - l + 1);
}

void del(int val, int l, int r) {
    st.erase(st.find({val, l, r}));
    update(1, 1, 200000, val, -(r - l + 1));
}

int rev[2000005];

vector<pair<int, int>> queries[2000005];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("abracadabra.in.1a", "r", stdin);
//    freopen("", "w", stdout);

    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        rev[a[i]] = i;
    }

    for (int i = 0; i < q; i++) {
        int t, j; cin >> t >> j;
        if (t == 0) {
            ans[i] = a[j];
        } else queries[min(t, n)].push_back(pair{i, j});
    }

    vector<int> big(n + 1, n + 1);
    stack<int> stk;
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && a[stk.top()] < a[i]) {
            big[stk.top()] = i;
            stk.pop();
        }

        stk.push(i);
    }

    for (int i = 1; i <= n; ) {
        add(a[i], i, big[i] - 1);
        i = big[i];
    }

    for (int i = 1; i <= n; i++) {
        int idx = walk(1, 1, 200000, n / 2 + 1);

        // index of first on RHS

        if (sum(1, 1, 200000, 1, idx - 1) < n / 2) {
            // need update then

            // segment to remove
            auto seg = *st.lower_bound({idx, 0, 0});
            int lastidx = seg[1] + (n / 2 - sum(1, 1, 200000, 1, idx - 1)) - 1;

            del(seg[0], seg[1], seg[2]);
            add(seg[0], seg[1], lastidx);

            lastidx++;

            while (big[lastidx] <= seg[2]) {
                add(a[lastidx], lastidx, big[lastidx] - 1);
                lastidx = big[lastidx];
            }

            add(a[lastidx], lastidx, seg[2]);
        }

        for (auto [idx, v] : queries[i]) {
            int curidx = walk(1, 1, 200000, v);
            int have = sum(1, 1, 200000, 1, curidx - 1);

            int delta = v - have - 1;

            ans[idx] = a[rev[curidx] + delta];
        }

    }

    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 70384 KB Output is correct
2 Correct 374 ms 69612 KB Output is correct
3 Correct 351 ms 68940 KB Output is correct
4 Correct 294 ms 68664 KB Output is correct
5 Correct 315 ms 71760 KB Output is correct
6 Correct 294 ms 72068 KB Output is correct
7 Correct 325 ms 72188 KB Output is correct
8 Correct 311 ms 69944 KB Output is correct
9 Correct 292 ms 69072 KB Output is correct
10 Correct 314 ms 69028 KB Output is correct
11 Correct 299 ms 68980 KB Output is correct
12 Correct 270 ms 65836 KB Output is correct
13 Correct 301 ms 67304 KB Output is correct
14 Correct 311 ms 71884 KB Output is correct
15 Correct 306 ms 68992 KB Output is correct
16 Correct 25 ms 47316 KB Output is correct
17 Correct 183 ms 60516 KB Output is correct
18 Correct 242 ms 64064 KB Output is correct
19 Correct 23 ms 47316 KB Output is correct
20 Correct 22 ms 47268 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 97056 KB Output is correct
2 Correct 485 ms 95264 KB Output is correct
3 Correct 478 ms 88784 KB Output is correct
4 Correct 371 ms 77548 KB Output is correct
5 Correct 407 ms 78428 KB Output is correct
6 Correct 374 ms 78708 KB Output is correct
7 Correct 419 ms 80684 KB Output is correct
8 Correct 414 ms 82440 KB Output is correct
9 Correct 370 ms 77308 KB Output is correct
10 Correct 388 ms 78944 KB Output is correct
11 Correct 314 ms 73044 KB Output is correct
12 Correct 321 ms 73220 KB Output is correct
13 Correct 374 ms 78360 KB Output is correct
14 Correct 330 ms 76244 KB Output is correct
15 Correct 387 ms 81248 KB Output is correct
16 Correct 72 ms 52788 KB Output is correct
17 Correct 295 ms 80708 KB Output is correct
18 Correct 278 ms 69936 KB Output is correct
19 Correct 99 ms 55756 KB Output is correct
20 Correct 139 ms 58580 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 60748 KB Output is correct
2 Correct 134 ms 59584 KB Output is correct
3 Correct 168 ms 59848 KB Output is correct
4 Correct 91 ms 53836 KB Output is correct
5 Correct 138 ms 56092 KB Output is correct
6 Correct 96 ms 53968 KB Output is correct
7 Correct 118 ms 55036 KB Output is correct
8 Correct 100 ms 54480 KB Output is correct
9 Correct 118 ms 55648 KB Output is correct
10 Correct 78 ms 53000 KB Output is correct
11 Correct 83 ms 52980 KB Output is correct
12 Correct 79 ms 53096 KB Output is correct
13 Correct 81 ms 53056 KB Output is correct
14 Correct 81 ms 53316 KB Output is correct
15 Correct 77 ms 52420 KB Output is correct
16 Correct 45 ms 49996 KB Output is correct
17 Correct 88 ms 57348 KB Output is correct
18 Correct 67 ms 51248 KB Output is correct
19 Correct 22 ms 47244 KB Output is correct
20 Correct 23 ms 47280 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 70384 KB Output is correct
2 Correct 374 ms 69612 KB Output is correct
3 Correct 351 ms 68940 KB Output is correct
4 Correct 294 ms 68664 KB Output is correct
5 Correct 315 ms 71760 KB Output is correct
6 Correct 294 ms 72068 KB Output is correct
7 Correct 325 ms 72188 KB Output is correct
8 Correct 311 ms 69944 KB Output is correct
9 Correct 292 ms 69072 KB Output is correct
10 Correct 314 ms 69028 KB Output is correct
11 Correct 299 ms 68980 KB Output is correct
12 Correct 270 ms 65836 KB Output is correct
13 Correct 301 ms 67304 KB Output is correct
14 Correct 311 ms 71884 KB Output is correct
15 Correct 306 ms 68992 KB Output is correct
16 Correct 25 ms 47316 KB Output is correct
17 Correct 183 ms 60516 KB Output is correct
18 Correct 242 ms 64064 KB Output is correct
19 Correct 23 ms 47316 KB Output is correct
20 Correct 22 ms 47268 KB Output is correct
21 Correct 609 ms 97056 KB Output is correct
22 Correct 485 ms 95264 KB Output is correct
23 Correct 478 ms 88784 KB Output is correct
24 Correct 371 ms 77548 KB Output is correct
25 Correct 407 ms 78428 KB Output is correct
26 Correct 374 ms 78708 KB Output is correct
27 Correct 419 ms 80684 KB Output is correct
28 Correct 414 ms 82440 KB Output is correct
29 Correct 370 ms 77308 KB Output is correct
30 Correct 388 ms 78944 KB Output is correct
31 Correct 314 ms 73044 KB Output is correct
32 Correct 321 ms 73220 KB Output is correct
33 Correct 374 ms 78360 KB Output is correct
34 Correct 330 ms 76244 KB Output is correct
35 Correct 387 ms 81248 KB Output is correct
36 Correct 72 ms 52788 KB Output is correct
37 Correct 295 ms 80708 KB Output is correct
38 Correct 278 ms 69936 KB Output is correct
39 Correct 99 ms 55756 KB Output is correct
40 Correct 139 ms 58580 KB Output is correct
41 Correct 192 ms 60748 KB Output is correct
42 Correct 134 ms 59584 KB Output is correct
43 Correct 168 ms 59848 KB Output is correct
44 Correct 91 ms 53836 KB Output is correct
45 Correct 138 ms 56092 KB Output is correct
46 Correct 96 ms 53968 KB Output is correct
47 Correct 118 ms 55036 KB Output is correct
48 Correct 100 ms 54480 KB Output is correct
49 Correct 118 ms 55648 KB Output is correct
50 Correct 78 ms 53000 KB Output is correct
51 Correct 83 ms 52980 KB Output is correct
52 Correct 79 ms 53096 KB Output is correct
53 Correct 81 ms 53056 KB Output is correct
54 Correct 81 ms 53316 KB Output is correct
55 Correct 77 ms 52420 KB Output is correct
56 Correct 45 ms 49996 KB Output is correct
57 Correct 88 ms 57348 KB Output is correct
58 Correct 67 ms 51248 KB Output is correct
59 Correct 22 ms 47244 KB Output is correct
60 Correct 23 ms 47280 KB Output is correct
61 Correct 900 ms 100344 KB Output is correct
62 Correct 710 ms 98400 KB Output is correct
63 Correct 820 ms 95944 KB Output is correct
64 Correct 599 ms 86348 KB Output is correct
65 Correct 684 ms 89180 KB Output is correct
66 Correct 607 ms 86336 KB Output is correct
67 Correct 523 ms 84184 KB Output is correct
68 Correct 524 ms 84500 KB Output is correct
69 Correct 604 ms 85884 KB Output is correct
70 Correct 482 ms 81860 KB Output is correct
71 Correct 445 ms 83440 KB Output is correct
72 Correct 495 ms 80600 KB Output is correct
73 Correct 457 ms 81484 KB Output is correct
74 Correct 473 ms 84156 KB Output is correct
75 Correct 496 ms 81640 KB Output is correct
76 Correct 71 ms 52300 KB Output is correct
77 Correct 323 ms 79992 KB Output is correct
78 Correct 322 ms 71620 KB Output is correct
79 Correct 22 ms 47308 KB Output is correct
80 Correct 22 ms 47356 KB Output is correct