Submission #918794

#	Time	Username	Problem	Language	Result	Execution time	Memory
918794		JakobZorz	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	507 ms	49488 KiB

Main

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

const int TREE_SIZE=1<<18;

int n;
int l[200001];
int r[200001];
int tree[2*TREE_SIZE];

vector<int>init;

void update(int i,int val){
    i+=TREE_SIZE;
    tree[i]=val;
    i/=2;
    while(i){
        tree[i]=tree[2*i]+tree[2*i+1];
        i/=2;
    }
}

pair<int,int>get(int node,int rl,int rr,int sum){
    if(tree[node]<=sum)
        return{rr,tree[node]};
    
    if(rl==rr-1)
        return{rl,0};
    
    int mid=(rl+rr)/2;
    if(sum<tree[2*node])
        return get(2*node,rl,mid,sum);
    else{
        auto res=get(2*node+1,mid,rr,sum-tree[2*node]);
        res.second+=tree[2*node];
        return res;
    }
}

void insert(int a,int b){
    l[init[a]]=a;
    r[init[a]]=b;
    update(init[a],b-a);
}

pair<int,int>get(int sum){
    auto res=get(1,0,TREE_SIZE,sum);
    return{res.first,sum-res.second};
}

void solve(){
    int q;
    cin>>n>>q;
    init.resize(n);
    vector<int>nxt(n);
    for(int&i:init)
        cin>>i;
    
    stack<pair<int,int>>st;
    st.push({n+1,n});
    for(int i=n-1;i>=0;i--){
        while(st.top().first<init[i])
            st.pop();
        nxt[i]=st.top().second;
        st.push({init[i],i});
    }
    
    vector<vector<pair<int,int>>>qrs(n+1);
    vector<int>ans(q,-1);
    for(int i=0;i<q;i++){
        int t,qi;
        cin>>t>>qi;
        t=min(t,n);
        qrs[t].push_back({qi-1,i});
    }
    
    for(int curr=0;curr<n;){
        insert(curr,nxt[curr]);
        curr=nxt[curr];
    }
    
    for(int round=0;round<=n;round++){
        for(auto i:qrs[round]){
            auto res=get(i.first);
            
            ans[i.second]=init[l[res.first]+res.second];
        }
        
        auto res=get(n/2);
        
        if(res.second==0)
            continue;
        
        int nl=l[res.first]+res.second;
        int nr=r[res.first];
        insert(l[res.first],nl);
        
        for(int curr=nl;curr<nr;){
            int nx=min(nxt[curr],nr);
            insert(curr,nx);
            curr=nx;
        }
    }
    
    for(int i:ans){
        if(i==-1)
            abort();
        cout<<i<<"\n";
    }
}
 
int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("input.in","r",stdin);freopen("output.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}

/*
6 3
1 5 6 2 3 4
1 2
0 4
1 5
 
2
2
5
 

6 6
2 1 5 4 6 3
0 1
1 1
0 3
1 3
0 6
10 6
 
2
2
5
4
3
3
 

10 10
7 5 2 9 10 8 4 3 6 1
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
 
2
3
6
1
7
5
8
4
9
10
 
10 10
5 4 3 10 9 8 7 6 2 1
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
 
1
2
5
4
3
6
8
7
10
9
 
 */

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