Submission #861205

#	Time	Username	Problem	Language	Result	Execution time	Memory
861205		vgtcross	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	618 ms	58368 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct segtree {
    int v;
    int l, r, m;
    segtree *lc = nullptr, *rc = nullptr;
    
    segtree(int L, int R, vector<int> &u) {
        l = L;
        r = R;
        m = (l + r) / 2;
        if (l == r) {
            v = u[m];
            return;
        }
        
        lc = new segtree(l, m, u);
        rc = new segtree(m+1, r, u);
        v = lc->v + rc->v;
    }
    
    void point_set(int i, int k) {
        if (l == i && i == r) {
            v = k;
            return;
        }
        if (i <= m) lc->point_set(i, k);
        else rc->point_set(i, k);
        v = lc->v + rc->v;
    }
    
    pii get_val(int i) {
        if (l == r) return {m, i};
        if (i < lc->v) return lc->get_val(i);
        else return rc->get_val(i - lc->v);
    }
    
    void del() {
        if (lc != nullptr) lc->del();
        if (rc != nullptr) rc->del();
        delete lc;
        delete rc;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    
    vector<int> a(n+1, n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        --a[i];
    }
    vector<int> b(n+1);
    for (int i = 0; i <= n; ++i) b[a[i]] = i;
    
    vector<array<int, 3>> que(q);
    for (int i = 0; i < q; ++i) {
        cin >> que[i][0] >> que[i][1];
        que[i][2] = i;
    }
    
    vector<int> nx(n+1);
    stack<int> st;
    for (int i : a) {
        while (st.size() && i > st.top()) {
            nx[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while (st.size()) {
        nx[st.top()] = n;
        st.pop();
    }
    
    vector<int> len(n, 0);
    for (int i = a[0]; i < n; i = nx[i]) len[i] = b[nx[i]] - b[i];
    
    segtree seg(0, n-1, len);
    
    sort(que.begin(), que.end());
    vector<int> ans(q);
    
    int j = 0;
    for (int i = 0; true; ++i) {
        while (j < q && que[j][0] == i) {
            pii p = seg.get_val(que[j][1]-1);
            ans[que[j][2]] = a[b[p.first] + p.second];
            ++j;
        }
        
        pii p = seg.get_val(n / 2);
        if (p.second == 0) break;
        for (int k = a[b[p.first] + p.second]; b[k] < b[p.first] + len[p.first]; k = nx[k]) {
            len[k] = min(b[nx[k]], b[p.first] + len[p.first]) - b[k];
            seg.point_set(k, len[k]);
        }
        len[p.first] = p.second;
        seg.point_set(p.first, len[p.first]);
    }
    
    while (j < q) {
        pii p = seg.get_val(que[j][1]-1);
        ans[que[j][2]] = a[b[p.first] + p.second];
        ++j;
    }
    
    for (int i = 0; i < q; ++i) cout << ans[i]+1 << '\n';
    
    seg.del();
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

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