Submission #1014464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014464		shiomusubi496	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	1610 ms	52712 KiB

Main

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(v) begin(v), end(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

class BinaryIndexedTree {
    int n;
    vector<int> dat;

public:
    BinaryIndexedTree(int n_) : n(n_), dat(n_ + 1, 0) {}
    void add(int k, ll x) {
        ++k;
        while (k <= n) {
            dat[k] += x;
            k += k & -k;
        }
    }
    ll sum(int k) const {
        ll res = 0;
        while (k > 0) {
            res += dat[k];
            k -= k & -k;
        }
        return res;
    }
    ll sum(int l, int r) const { return sum(r) - sum(l); }

    ll get(int k) const { return sum(k, k + 1); }

    template<class F> int max_right(F&& f) const {
        int x = 0;
        ll w = 0;
        for (int k = 1 << 20; k > 0; k >>= 1) {
            if (x + k <= n && f(w + dat[x + k])) {
                w += dat[x + k];
                x += k;
            }
        }
        return x;
    }
};

int main() {
    int N, Q; cin >> N >> Q;
    vector<int> A(N);
    rep (i, N) cin >> A[i];
    rep (i, N) --A[i];
    int M = 2 * N;
    vector<vector<pair<int, int>>> query(M);
    vector<int> ans(Q, -1);
    rep (i, Q) {
        int t, k; cin >> t >> k;
        chmin(t, M);
        --k;
        if (t == 0) ans[i] = A[k];
        else query[t - 1].emplace_back(k, i);
    }

    vector<int> nxt(N, N); // 自分より大きい最初の要素
    vector<int> len(N); // prefix で最大値を取るものについて、それが支配する区間の長さ
    {
        stack<int> st{{N}};
        rrep (i, N) {
            while (st.top() != N && A[st.top()] < A[i]) st.pop();
            nxt[i] = st.top();
            st.push(i);
        }
        while (st.top() != N) {
            len[st.top()] = nxt[st.top()] - st.top();
            st.pop();
        }
    }

    vector<int> Arev(N);
    rep (i, N) Arev[A[i]] = i;

    BinaryIndexedTree bit(N);
    rep (i, N) bit.add(A[i], len[i]);

    for (auto qs : query) {
        int a = bit.max_right([&](int w) { return w <= N / 2; });
        int t = N / 2 - bit.sum(a);
        a = Arev[a];
        if (t) {
            // A[a] が支配する区間が分割される
            int l = a + len[a];
            bit.add(A[a], t - len[a]);
            len[a] = t;
            a += t;
            while (a < l) {
                int na = min(nxt[a], l);
                bit.add(A[a], na - a);
                len[a] = na - a;
                a = na;
            }
        }
        for (auto [k, i] : qs) {
            int a = bit.max_right([&](int w) { return w <= k; });
            int t = k - bit.sum(a);
            a = Arev[a];
            ans[i] = A[a + t];
        }
    }
    for (auto i : ans) cout << i + 1 << endl;
}

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