Submission #1189393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189393		Unforgettablepl	Abracadabra (CEOI22_abracadabra)	C++20	100 / 100	504 ms	52168 KiB

Main

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

#define int long long

struct fenwick{
    vector<int> tree;
    fenwick(int N):tree(N+1){}
    void add(int k,int x){
        while(k<tree.size()){
            tree[k]+=x;
            k+=k&-k;
        }
    }
    int get(int k){
        int ans = 0;
        while(k){
            ans+=tree[k];
            k-=k&-k;
        }
        return ans;
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,Q;
    cin >> N >> Q;
    vector<int> arr(N+1);
    vector<int> optR(N+1);
    vector<int> idx(N+1);
    for(int i=1;i<=N;i++){
        cin>>arr[i];
        idx[arr[i]]=i;
    }
    {
        stack<pair<int,int>> s;
        s.emplace(N+1,N+1);
        for(int i=N;i;i--){
            while(s.top().first<arr[i])s.pop();
            optR[i]=s.top().second;
            s.emplace(arr[i],i);
        }
    }
    vector<vector<pair<int,int>>> queries(N+1);
    vector<int> ans(Q+1);
    for(int i=1;i<=Q;i++){
        int t,x;cin>>t>>x;
        queries[min(t,N)].emplace_back(x,i);
    }
    for(auto&[pos,id]:queries[0])ans[id]=arr[pos];
    fenwick bit(N);
    auto solve = [&](int L,int R){
        while(L<=R){
            int upd = min(optR[L],R+1);
            bit.add(arr[L],upd-L);
            L = upd;
        }
    };
    solve(1,N/2);
    solve(N/2 + 1,N);
    for(int round = 1;round<=N;round++){
        for(auto&[pos,id]:queries[round]){
            int higher = 0;
            for(int jump=(1<<17);jump;jump/=2){
                if(higher+jump>N)continue;
                if(bit.get(higher+jump)<pos)higher+=jump;
            }
            int prev = bit.get(higher);
            ans[id]=arr[pos-prev-1+idx[higher+1]];
        }
        int ele = 0;
        for(int jump=(1<<17);jump;jump/=2){
            if(ele+jump>N)continue;
            if(bit.get(ele+jump)<N/2)ele+=jump;
        }
        int prev = bit.get(ele);
        ele++;
        int L = N/2-prev+idx[ele];
        int R = bit.get(ele)-prev-1+idx[ele];
        solve(L,R);
        bit.add(ele,-(R-L+1));
    }
    for(int i=1;i<=Q;i++)cout<<ans[i]<<'\n';
}

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