Submission #1225467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225467		AlperenT_	Abracadabra (CEOI22_abracadabra)	C++20	100 / 100	566 ms	113256 KiB

Main

#include <bits/stdc++.h> 

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<ll,ll> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld long double
#define ll long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e6  , maxk = 100 + 10  , inf = 1e9+ 10 , mod = 1e9 + 9 ;
int mark[maxn] , ri[maxn] , ans[maxn]  ;
int seg[4*maxn] ;
 int n , q ;
void upd(int x, int w, int p =1 ,int l =1  ,int r = n){
    int mid  =(l+r)/2 , pl =p<<1 ,pr=p<<1|1 ;
    if(l >x || x > r)return; 
    if(l==r){
        seg[p] = w; 
        return ;
    }
    upd(x,w,pl,l,mid);
    upd(x,w,pr,mid+1,r);
    seg[p] = seg[pl] + seg[pr] ;
}
int que(int le , int ri , int p =1 ,int l =1  ,int r = n){
    int mid  =(l+r)/2 , pl =p<<1 ,pr=p<<1|1 ;
    if(l >ri || le > r)return 0 ; 
    if(le <= l && r <= ri){
        return seg[p] ; 
    }
    return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r) ;
}
int find(int x ,int p =1 ,int l= 1, int r= n){
    int mid = (l+r)/2 , pl =p << 1, pr =p<<1|1 ;
    if(l == r)return l ;
    if(seg[pl] < x){
        x-=seg[pl] ;
        return find(x,pr,mid+1,r);
    }
    return find(x,pl,l,mid);     
}
int p[maxn] , a[maxn];
vector <pii> qu[maxn] ;
signed main(){
    ios_base::sync_with_stdio(0) ;cin.tie(0) ;
    cin >> n >> q; 
    rep(i ,1, n ){
        cin >> a[i] ;
        p[a[i]] = i ;
    }
    rep(i ,1, q){
        int t , x; 
        cin >> t >> x; 
        t = min(t , n+1) ;
        qu[t].pb({x,i}) ;
    }
    vector <int> vec; 
    int ls =n+1; 
    per(i , n ,1){
        while(sz(vec) && a[vec.back()] <= a[i])vec.pop_back();
        if(sz(vec) == 0){
            ri[i] = n+1;
        }else{
            ri[i] = vec.back() ;
        }
        vec.pb(i);
    }
    int mx = 0 ;
    rep(i ,1, n){
        if(a[i]  > a[mx]){
            mark[a[i]] =1 ;
            if(mx!=0)upd(a[mx] , i-mx) ;
            mx = i ;
        }
    }
    ri[n+1]= n+2; 
    mark[n] =1; 
    upd(n , n-mx+1) ;
    rep(i ,0 , n+1){
        for(auto [x,id] : qu[i]){
            int z = find(x) ;
            ans[id] = a[p[z] + x-que( 1, z-1) -1] ; 
        }
        int x = find(n/2);
        if(que(1,x)!=n/2){
            int id = p[x] + n/2-que(1,x-1)  ;
            vector <int> vec; 
            while(id <= n+1){
                vec.pb(id) ;
                if(mark[a[id]] == 1)break ;
                id = ri[id] ;        
            }
            rep(i , 0 ,sz(vec)-2){
                mark[a[vec[i]]] = 1; 
                if(i != sz(vec)-2){
                    upd(a[vec[i]] , vec[i+1]-vec[i]) ;
                }else{
                    upd(a[vec[i]] , que(x,x)-(vec[i]-p[x]) ) ;
                }
            }
            upd(x , vec[0]-p[x]) ;
        }
    }
    rep(i ,1, q){
        cout << ans[i] << "\n";
    }
}

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