Submission #725799

#	Time	Username	Problem	Language	Result	Execution time	Memory
725799		tengiz05	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	1964 ms	50272 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 200000;
constexpr int B = 300;

struct DataStructure {
    int n;
    std::vector<int> a;
    std::vector<int> nxt;
    std::vector<std::pair<int, int>> blocks;
    std::deque<std::pair<int, int>> d[N / B + 2];
    int siz[N / B + 2];
    bool FirstTime;
    DataStructure(std::vector<int> a, std::vector<int> nxt, std::vector<std::pair<int, int>> blocks) : n(a.size()), a(a), nxt(nxt), blocks(blocks) {
        FirstTime = true;
        memset(siz, 0, sizeof siz);
    }
    int at(int p) {
        if (FirstTime) {
            return a[p];
        }
        int cursiz = 0;
        for (int cur = 0; ; cur++) {
            if (cursiz + siz[cur] > p) {
                int id = 0;
                for (auto [l, r] : d[cur]) {
                    cursiz += r - l;
                    if (cursiz > p) {
                        cursiz -= r - l;
                        return a[l + p - cursiz];
                    }
                    id++;
                }
            }
            cursiz += siz[cur];
        }
    }
    void insert(int L, int R) {
        //~ std::cerr << "Divided: " << L << " " << R << "\n";
        for (int cur = 0; ; cur++) {
            if (d[cur + 1].empty() || a[d[cur + 1][0].first] > a[L]) {
                int k = d[cur].size();
                for (int i = 0; i <= k; i++) {
                    if (i == k || a[d[cur][i].first] > a[L]) {
                        d[cur].insert(d[cur].begin() + i, {L, R});
                        siz[cur] += R - L;
                        break;
                    }
                }
                while (d[cur].size() > B) {
                    int s = d[cur].back().second - d[cur].back().first;
                    siz[cur + 1] += s;
                    d[cur + 1].push_front(d[cur].back());
                    siz[cur] -= s;
                    d[cur].pop_back();
                    cur++;
                }
                break;
            }
        }
    }
    void nextShuffle() {
        if (FirstTime) {
            std::sort(blocks.begin(), blocks.end(), [&](const auto &i, const auto &j) {
                return a[i.first] < a[j.first];
            });
            int cur = 0;
            for (auto [l, r] : blocks) {
                d[cur].push_back({l, r});
                siz[cur] += r - l;
                if (d[cur].size() == B) {
                    cur++;
                }
            }
            FirstTime = false;
            return;
        }
        int cursiz = 0;
        int L = -1, R = -1;
        int savecur = -1, saveid = -1;
        for (int cur = 0; ; cur++) {
            if (cursiz + siz[cur] > n / 2) {
                int id = 0;
                for (auto [l, r] : d[cur]) {
                    cursiz += r - l;
                    if (cursiz > n / 2) {
                        L = l;
                        R = r;
                        savecur = cur;
                        saveid = id;
                        break;
                    }
                    id++;
                }
                break;
            }
            cursiz += siz[cur];
        }
        //~ std::cerr << L << " " << R << "::\n";
        cursiz -= R - L;
        if (cursiz == n / 2) return;
        int mid = n / 2 - cursiz + L;
        // removal of the midBlock
        siz[savecur] -= R - L;
        d[savecur].erase(d[savecur].begin() + saveid);
        for (int i = savecur + 1; !d[i].empty(); i++) {
            //~ std::cerr << "Red flag\n";
            int s = d[i].front().second - d[i].front().first;
            siz[i - 1] += s;
            d[i - 1].push_back(d[i].front());
            siz[i] -= s;
            d[i].pop_front();
        }
        // division of the midBlock
        for (int i = L; i < mid; i = nxt[i]) {
            insert(i, std::min(mid, nxt[i]));
        }
        for (int i = mid; i < R; i = nxt[i]) {
            insert(i, std::min(R, nxt[i]));
        }
        //~ for (auto [l, r] : d[0]) {
            //~ std::cout << l << " " << r << "\n";
        //~ }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i]--;
    }
    
    std::vector<std::vector<std::pair<int, int>>> Q(n + 1);
    std::vector<int> ans(q);
    for (int i = 0; i < q; i++) {
        int t, p;
        std::cin >> t >> p;
        t = std::min(t, n);
        p--;
        Q[t].push_back({p, i});
    }
    
    std::vector<int> nxt(n);
    std::vector<int> st{n};
    for (int i = n - 1; i >= 0; i--) {
        while (st.back() < n && a[st.back()] < a[i]) {
            st.pop_back();
        }
        nxt[i] = st.back();
        st.push_back(i);
    }
    
    std::vector<std::pair<int, int>> blocks;
    for (int i = 0; i < n / 2; i = nxt[i]) {
        blocks.push_back({i, std::min(n / 2, nxt[i])});
    }
    for (int i = n / 2; i < n; i = nxt[i]) {
        blocks.push_back({i, nxt[i]});
    }
    DataStructure D(a, nxt, blocks);
    for (int t = 0; t <= n; t++) {
        //~ std::cerr << "Stage " << t << ";\n";
        for (auto [p, id] : Q[t]) {
            ans[id] = D.at(p);
        }
        D.nextShuffle();
    }
    
    for (int i = 0; i < q; i++) {
        std::cout << ans[i] + 1 << "\n";
    }
    
    return 0;
}

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