Submission #656854

#	Time	Username	Problem	Language	Result	Execution time	Memory
656854		dooompy	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	900 ms	100344 KiB

Main

#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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25