Submission #633604

#	Time	Username	Problem	Language	Result	Execution time	Memory
633604		Ooops_sorry	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	1383 ms	57360 KiB

Main

#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(51);

#define ll long long
#define pb push_back
#define ld long double

const int N = 2e5 + 10;
int pos[N];

struct SegTree {
    vector<int> t;
    SegTree(int n) {
        t.resize(4 * n);
    }
    void update(int v, int l, int r, int pos, int val) {
        if (l == r) {
            t[v] += val;
            return;
        }
        int m = (l + r) / 2;
        if (pos <= m) {
            update(2 * v, l, m, pos, val);
        } else {
            update(2 * v + 1, m + 1, r, pos, val);
        }
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
    int get_ind(int v, int l, int r, int val) {
        if (l == r) {
            return l;
        }
        int m = (l + r) / 2;
        if (t[v * 2] >= val) {
            return get_ind(2 * v, l, m, val);
        } else {
            return get_ind(2 * v + 1, m + 1, r, val - t[v * 2]);
        }
    }
    int get_sum(int v, int tl, int tr, int l, int r) {
        if (l > r) return 0;
        if (tl == l && tr == r) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        return get_sum(2 * v, tl, tm, l, min(r, tm)) + get_sum(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
    }
} t(N);

set<array<int, 3>> st;

void add_seg(int val, int l, int r) {
    st.insert({val, l, r});
    t.update(1, 0, N - 1, val, (r - l + 1));
}

void del_seg(int val, int l, int r) {
    st.erase({val, l, r});
    t.update(1, 0, N - 1, val, -(r - l + 1));
}

int get_ind(int need) {
    return pos[t.get_ind(1, 0, N - 1, need)];
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n), ans(q, -1), go(n, n);
    vector<vector<pair<int,int>>> need(n);
    int last = 0;
    deque<int> qu;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
        if (a[i] > a[last]) {
            add_seg(a[last], last, i - 1);
            last = i;
        }
    }
    for (int i = 0; i < n; i++) {
        while (qu.size() > 0 && a[i] > a[qu.back()]) {
            go[qu.back()] = i;
            qu.pop_back();
        }
        qu.pb(i);
    }
    add_seg(a[last], last, n - 1);
    for (int i = 0; i < q; i++) {
        int t, ind;
        cin >> t >> ind;
        if (t == 0) {
            ans[i] = a[ind - 1];
        } else {
            need[min(n - 1, t - 1)].pb({ind, i});
        }
    }
    for (int i = 0; i < n; i++) {
        int pos = get_ind(n / 2 + 1);
        if (t.get_sum(1, 0, N - 1, 0, a[pos] - 1) < n / 2) {
            auto seg = *st.lower_bound({a[pos], 0, 0});
            int ind = seg[2] - (t.get_sum(1, 0, N - 1, 0, a[pos]) - n / 2);
            del_seg(seg[0], seg[1], seg[2]);
            add_seg(seg[0], seg[1], ind);
            int last = ind + 1;
            while (go[last] <= seg[2]) {
                add_seg(a[last], last, go[last] - 1);
                last = go[last];
            }
            add_seg(a[last], last, seg[2]);
        }
        for (auto to : need[i]) {
            int pos = get_ind(to.first);
            auto seg = *st.lower_bound({a[pos], 0, 0});
            ans[to.second] = a[seg[2] - (t.get_sum(1, 0, N - 1, 0, a[pos]) - to.first)];
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25