Submission #1288171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288171		stefanneagu	Abracadabra (CEOI22_abracadabra)	C++20	100 / 100	712 ms	63432 KiB

Main

#include <bits/stdc++.h>
// #define int long long

using namespace std;

const int nmax = 2e6 + 1;

int v[nmax];
int ng[nmax];
int n;

struct aib {
    int aib[nmax];

    void upd(int a, int val) {
        while (a < nmax) {
            aib[a] += val;
            a += (a & (-a));
        }
    }

    int qry(int a) {
        if (a == 0) return 0;
        int ans = 0;
        while (a > 0) {
            ans += aib[a];
            a -= (a & (-a));
        }
        return ans;
    }
} aib1, aib2;

void next_gr() {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && v[st.top()] < v[i]) {
            ng[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while (!st.empty()) {
        ng[st.top()] = n + 1;
        st.pop();
    }
}

void build(int l, int r, vector<pair<int, int>> &vv) {
    while (l <= r) {
        if (ng[l] - 1 < r) {
            vv.push_back({l, ng[l] - 1});
            l = ng[l];
        } else {
            vv.push_back({l, r});
            return;
        }
    }
}

void build2(int l, int r, vector<array<int, 3>> &vv) {
    while (l <= r) {
        if (ng[l] - 1 < r) {
            vv.push_back({v[l], l, ng[l] - 1});
            l = ng[l];
        } else {
            vv.push_back({v[l], l, r});
            return;
        }
    }
}

struct qry {
    int t, loc;
} qq[nmax];

vector<pair<int, int>> qrs[nmax];
int ans[nmax];

set<int> in1, in2;

pair<int, int> solve1(int loc) {
    int st = 1, dr = n, ans = -1, plm = -1;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        int cur = aib1.qry(mid);
        if (cur >= loc) {
            plm = cur;
            ans = mid;
            dr = mid - 1;
        } else {
            st = mid + 1;
        }
    }
    return {ans, (aib1.qry(ans) - aib1.qry(ans - 1)) - (plm - loc) - 1};
}

pair<int, int> solve2(int loc) {
    int st = 1, dr = n, ans = -1, plm = -1;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        int cur = aib2.qry(mid);
        if (cur >= loc) {
            plm = cur;
            ans = mid;
            dr = mid - 1;
        } else {
            st = mid + 1;
        }
    }
    return {ans, (aib2.qry(ans) - aib2.qry(ans - 1)) - (plm - loc) - 1};
}

int back[nmax];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        back[v[i]] = i;
    }
    for (int i = 1; i <= q; i++) {
        cin >> qq[i].t >> qq[i].loc;
        if (qq[i].t == 0) {
            ans[i] = v[qq[i].loc];
        } else {
            if (qq[i].t < nmax) {
                qrs[qq[i].t].push_back({qq[i].loc, i});
            }
        }
    }
    next_gr();
    vector<pair<int, int>> v1, v2;
    build(1, n / 2, v1);
    build(n / 2 + 1, n, v2);
    set<array<int, 3>> s1, s2;
    int iv1 = 0, iv2 = 0, sz1 = 0;
    while (iv1 < v1.size() || iv2 < v2.size()) {
        if (iv2 == v2.size() || (iv1 < v1.size() && v[v1[iv1].first] < v[v2[iv2].first])) {
            if (sz1 < n / 2) {
                sz1 += v1[iv1].second - v1[iv1].first + 1;
                s1.insert({v[v1[iv1].first], v1[iv1].first, v1[iv1].second});
                in1.insert(v[v1[iv1].first]);
                aib1.upd(v[v1[iv1].first], v1[iv1].second - v1[iv1].first + 1);
            } else {
                s2.insert({v[v1[iv1].first], v1[iv1].first, v1[iv1].second});
                in2.insert(v[v1[iv1].first]);
                aib2.upd(v[v1[iv1].first], v1[iv1].second - v1[iv1].first + 1);
            }
            iv1++;
        } else {
            if (sz1 < n / 2) {
                sz1 += v2[iv2].second - v2[iv2].first + 1;
                aib1.upd(v[v2[iv2].first], v2[iv2].second - v2[iv2].first + 1);
                in1.insert(v[v2[iv2].first]);
                s1.insert({v[v2[iv2].first], v2[iv2].first, v2[iv2].second});
            } else {
                aib2.upd(v[v2[iv2].first], v2[iv2].second - v2[iv2].first + 1);
                in2.insert(v[v2[iv2].first]);
                s2.insert({v[v2[iv2].first], v2[iv2].first, v2[iv2].second});
            }
            iv2++;
        }
    }
    for (auto [it, ind] : qrs[1]) {
        if (it <= sz1) {
            auto [haha, ramas] = solve1(it);
            ans[ind] = v[back[haha] + ramas];
        } else {
            auto [haha, ramas] = solve2(it - sz1);
            ans[ind] = v[back[haha] + ramas];
        }
    }
    for (int _ = 2; _ < nmax; _++) {
        vector<pair<int, int>> extra;
        if (sz1 == n / 2) break;
        while (sz1 > n / 2) {
            auto [val, l, r] = *s1.rbegin();
            s1.erase({val, l, r});
            in1.erase(val);
            aib1.upd(v[l], -(r - l + 1));
            if (sz1 - (r - l + 1) >= n / 2) {
                extra.push_back({l, r});
                sz1 -= r - l + 1;
            } else {
                int cat_mai_trebe = sz1 - n / 2;
                int rnou = r - cat_mai_trebe;
                s1.insert({val, l, rnou});
                in1.insert(val);
                aib1.upd(v[l], rnou - l + 1);
                extra.push_back({rnou + 1, r});
                break;
            }
        }
        vector<array<int, 3>> cur;
        for (auto it : extra) {
            build2(it.first, it.second, cur);
        }
        vector<array<int, 3>> pe1, pe2;
        int s1rbegin = (*s1.rbegin())[0];
        for (auto [val, l, r] : cur) {
            if (s1rbegin > val) {
                pe1.push_back({val, l, r});
            } else {
                pe2.push_back({val, l, r});
            }
        }
        for (auto it : pe1) {
            s1.insert(it);
            in1.insert(it[0]);
            aib1.upd(v[it[1]], it[2] - it[1] + 1);
        }
        for (auto it : pe2) {
            s2.insert(it);
            in2.insert(it[0]);
            aib2.upd(v[it[1]], it[2] - it[1] + 1);
        }
        for (auto [it, ind] : qrs[_]) {
            if (it <= sz1) {
                auto [haha, ramas] = solve1(it);
                ans[ind] = v[back[haha] + ramas];
             } else {
                auto [haha, ramas] = solve2(it - sz1);
                ans[ind] = v[back[haha] + ramas];
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        if (!ans[i]) {
            auto [it, ind] = pair<int, int>{qq[i].loc, i};
            if (it <= sz1) {
                auto [haha, ramas] = solve1(it);
                ans[ind] = v[back[haha] + ramas];
            } else {
                auto [haha, ramas] = solve2(it - sz1);
                ans[ind] = v[back[haha] + ramas];
            }
        }
        cout << ans[i] << '\n';
    }
    return 0;
}

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