Submission #918786

#	Time	Username	Problem	Language	Result	Execution time	Memory
918786		JakobZorz	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3053 ms	24372 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;

int n;
int l[200001];
int r[200001];
vector<int>init;

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

pair<int,int>get(int sum){
    for(int i=0;i<=n;i++){
        sum-=r[i]-l[i];
        if(sum<0)
            return{i,sum+r[i]-l[i]};
    }
    abort();
}

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 6
1 4 2 3 5 6
0 1
0 2
0 3
0 4
0 5
0 6

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

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
 
6 6
4 5 6 1 2 3
10 1
10 2
10 3
10 4
10 5
10 6
 
1
2
3
4
5
6
 
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: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25