oj.uz

Submission #855983

# Submission time Handle Problem Language Result Execution time Memory
855983 2023-10-02T13:24:56 Z Pannda Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 336 ms 33504 KB 
#include <bits/stdc++.h>
using namespace std;

const int LOG = 26;

struct Fenwick {
    int n;
    vector<int> bit;
    vector<int> a;
    Fenwick(int n) : n(n), bit(n + 1, 0), a(n, 0) {}

    void add(int i, int delta) {
        a[i] += delta;
        for (i++; i <= n; i += i & -i) {
            bit[i] += delta;
        }
    }

    int sum(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) {
            res += bit[i];
        }
        return res;
    }

    int get(int i) {
        return a[i];
    }

    int kth(int k) {
        int sum = 0;
        int cur = 0;
        for (int i = LOG - 1; i >= 0; i--) {
            if (cur + (1 << i) <= n && sum + bit[cur + (1 << i)] <= k) {
                cur += (1 << i);
                sum += bit[cur];
            }
        }
        return cur;
    }
};

const int T = (int)5e5;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n), ia(n);
    vector<vector<array<int, 2>>> mp(T);
    vector<int> ans(q);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        ia[a[i]] = i;
    }

    for (int id = 0; id < q; id++) {
        int t, i;
        cin >> t >> i;
        i--;
        t = min(t, T - 1);
        mp[t].push_back({ i, id });
    }

    Fenwick fen(n);
    for (int i = 0; i < n; ) {
        int anc = i;
        while (i < n && a[anc] >= a[i]) {
            i++;
        }
        int len = i - anc;
        fen.add(a[anc], len);
    }

    function<void()> cut = [&]() {
        int head = fen.kth(n / 2);
        int pos = fen.sum(head);
        int fromLen = fen.get(head);
        int toLen = n / 2 - pos;

        int newHead = a[ia[head] + toLen];
        int newLen = fromLen - toLen;

        fen.add(head, -fromLen + toLen);
        fen.add(newHead, newLen);
    };

    function<int(int)> kth = [&](int k) {
        int head = fen.kth(k);
        int pos = fen.sum(head);
        int toLen = k - pos;
        return a[ia[head] + toLen];
    };

    for (int t = 0; t < T; t++) {
        for (auto [i, id] : mp[t]) {
            ans[id] = kth(i);
        }
        cut();
    }

    for (auto x : ans) {
        cout << x + 1 << '\n';
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 30212 KB Output is correct
2 Correct 252 ms 29396 KB Output is correct
3 Correct 229 ms 28548 KB Output is correct
4 Correct 220 ms 28288 KB Output is correct
5 Correct 224 ms 30544 KB Output is correct
6 Correct 220 ms 31248 KB Output is correct
7 Incorrect 230 ms 31748 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 33504 KB Output is correct
2 Correct 314 ms 33464 KB Output is correct
3 Correct 252 ms 30392 KB Output is correct
4 Correct 239 ms 31192 KB Output is correct
5 Correct 239 ms 30960 KB Output is correct
6 Correct 243 ms 30248 KB Output is correct
7 Incorrect 266 ms 33408 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 16720 KB Output is correct
2 Correct 89 ms 16212 KB Output is correct
3 Correct 87 ms 16284 KB Output is correct
4 Correct 80 ms 16008 KB Output is correct
5 Correct 73 ms 16380 KB Output is correct
6 Correct 69 ms 15956 KB Output is correct
7 Incorrect 62 ms 16212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 30212 KB Output is correct
2 Correct 252 ms 29396 KB Output is correct
3 Correct 229 ms 28548 KB Output is correct
4 Correct 220 ms 28288 KB Output is correct
5 Correct 224 ms 30544 KB Output is correct
6 Correct 220 ms 31248 KB Output is correct
7 Incorrect 230 ms 31748 KB Output isn't correct
8 Halted 0 ms 0 KB -