제출 #1226270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226270		spetr	Abracadabra (CEOI22_abracadabra)	C++20	100 / 100	577 ms	55328 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

vl tree;
vl hranice;
vl nums;
ll velikost;

void update(ll l, ll L, ll R, ll c, ll i){
    if (L == R){
        tree[i] += c;
        return;
    }
    ll mid = (L + R) / 2;
    if (l <= mid) update(l, L, mid, c, 2*i + 1);
    else update(l, mid+1, R, c, 2*i + 2);
    tree[i] = tree[2*i + 1] + tree[2*i + 2];
}

ll secti(ll l, ll r, ll L, ll R, ll i){
    if (r < L || R < l) return 0;
    if (l <= L && R <= r) return tree[i];
    ll mid = (L + R) / 2;
    return secti(l, r, L, mid, 2*i + 1)
         + secti(l, r, mid+1, R, 2*i + 2);
}

ll target(ll t, ll i){
    ll L = 0, R = velikost - 1;
    ll pos = -1;
    while (L < R) {
        ll mid = (L + R) / 2;
        ll leftSum = tree[2*i + 1];
        if (leftSum < t) {
            t -= leftSum;
            pos = mid;
            i = 2*i + 2;
            L = mid + 1;
        } else {
            i = 2*i + 1;
            R = mid;
        }
    }
    return pos + 1;
}


void solve(ll l, ll r){
    ll i = l;
    while (i <= r){
        ll j = min(hranice[i], r+1);
        update(nums[i], 0, velikost-1, j - i, 0);
        i = j;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, q;
    cin >> n >> q;
    nums.resize(n);
    vl idx(n);
    for (ll i = 0; i < n; i++){
        ll num;
        cin >> num;
        num--;
        nums[i] = num;
        idx[num] = i;
    }

    for (velikost = 1; velikost < n; velikost *= 2);
    tree.resize(2*velikost-1, 0);
    hranice.resize(n, n);

    vl st;
    for (ll i = n-1; i >= 0; i--){
        while (!st.empty() && nums[st.back()] < nums[i]) st.pop_back();
        if (st.empty()){hranice[i] = n;} else hranice[i] = st.back(); 
        st.push_back(i);
    }

    vector<vector<pl>> queries(n+1);
    for (ll i = 0; i < q; i++){
        ll t, b;
        cin >> t >> b;
        queries[min(t, n)].push_back({b-1, i});
    }
    vl ans(q);

    for (auto &p : queries[0]){
        ans[p.second] = nums[p.first];
    }

    solve(0, n/2 - 1);
    solve(n/2, n-1);

    for (ll i = 1; i <= n; i++){

        for (auto p : queries[i]){
            ll pos = p.first;
            ll delka_bloku = target(pos+1, 0);
            ll pref = secti(0, delka_bloku-1, 0, velikost-1, 0);
            ll presah = pos - pref;
            ans[p.second] = nums[idx[delka_bloku] + presah];
        }
        ll delka_pul = target(n/2 + 1, 0);
        ll pref = secti(0, delka_pul-1, 0, velikost-1, 0);
        ll L = (n/2 - pref) + idx[delka_pul];
        ll R = (secti(0, delka_pul, 0, velikost-1, 0) - pref - 1) + idx[delka_pul];
        solve(L, R);
        update(delka_pul, 0, velikost-1, -(R - L + 1), 0);
    }

    for (ll i = 0; i < q; i++){
        cout << ans[i] + 1 << "\n";
    }
    return 0;
}

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