Submission #918759

#	Time	Username	Problem	Language	Result	Execution time	Memory
918759		JakobZorz	Abracadabra (CEOI22_abracadabra)	C++17	0 / 100	3061 ms	30444 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;
 
struct Query{
    int t,i,ord;
};

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;
}

void remove(int i){
    l[i]=0;
    r[i]=0;
}

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]};
    }
    return{-1,-1};
}

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<Query>>qrs(n+1);
    vector<int>ans(q);
    for(int i=0;i<q;i++){
        Query nq;
        nq.ord=i;
        cin>>nq.t>>nq.i;
        nq.t=min(nq.t,n);
        nq.i--;
        qrs[nq.t].push_back(nq);
    }
    
    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 r=get(i.i);
            
            ans[i.ord]=init[l[r.first]+r.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],l[res.first]+res.second);
        
        for(int curr=nl;curr<nr;){
            insert(curr,nxt[curr]);
            curr=nxt[curr];
        }
    }
    
    for(int i:ans){
        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;
}

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

1
4
2
3
5

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
 
 
 */

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