Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- //#define int long long
- #define mp make_pair
- #define pb push_back
- using namespace std;
- using namespace __gnu_pbds;
- mt19937 rnd(time(nullptr));
- constexpr int N = (int)1e6 + 111;
- constexpr int INF = (int)1e9 + 111;
- int T[4*N];
- int w[4*N];
- void push(int v,int l,int r){
- if(w[v] == 0)
- return;
- int m = (l+r)>>1;
- T[v<<1] += w[v];
- T[v<<1|1] += w[v];
- w[v<<1] += w[v];
- w[v<<1|1] += w[v];
- w[v] = 0;
- return;
- }
- void upd(int v,int l,int r,int tl,int tr,int x){
- if(l > r || tl > tr){
- return;
- }
- if(l == tl && r == tr){
- T[v] += x;
- w[v] += x;
- return;
- }
- push(v,l,r);
- int m = (l+r)>>1;
- upd(v<<1,l,m,tl,min(tr,m),x);
- upd(v<<1|1,m+1,r,max(tl,m+1),tr,x);
- T[v] = min(T[v<<1],T[v<<1|1]);
- return;
- }
- int n,q;
- void upd(int l,int r,int x){
- upd(1,1,n,l,r,x);
- return;
- }
- int get(int v,int l,int r,int tl,int tr){
- if(l > r || tl > tr)
- return INF;
- if(l == tl && r == tr)
- return T[v];
- push(v,l,r);
- int m = (l+r)>>1;
- return min(get(v<<1,l,m,tl,min(tr,m)),get(v<<1|1,m+1,r,max(m+1,tl),tr));
- }
- int get(int l,int r){
- return get(1,1,n,l,r);
- }
- int getPos(int v,int l,int r,int x){ /// get a[pos] <= x
- if(l > r)
- return -1;
- if(l == r)
- return l;
- int m = (l+r)>>1;
- push(v,l,r);
- if(T[v<<1] <= x)
- return getPos(v<<1,l,m,x);
- else
- return getPos(v<<1|1,m+1,r,x);
- }
- int getSuff(int r){
- return get(r,r);
- }
- int a[N];
- int t[N],P[N];
- set<int> st;
- int parent[N];
- vector<pair<int,pair<int,int>>> Q;
- int ans[N];
- int len[N];
- void __attribute__ (( optimize("Ofast","unroll-loops"), target("avx2") )) solve(){
- n = (int)10000, q = (int)10000;
- for(int i = 0; i <= n; i++) T[i] = 0;
- st.clear();
- Q.clear();
- cin >> n >> q;
- int rv[n+1];
- for(int i = 0; i < n; i++){
- cin >> a[i];
- rv[a[i]] = i;
- }
- int nxt[n+1];
- vector<pair<int,int>> RightBiggest;
- for(int i = n-1; i >= 0; i--){
- while(!RightBiggest.empty() && RightBiggest.back().first < a[i])
- RightBiggest.pop_back();
- if(!RightBiggest.empty())
- nxt[i] = RightBiggest.back().second;
- else
- nxt[i] = n;
- RightBiggest.pb(mp(a[i],i));
- }
- for(int i = 0; i < q; i++){
- cin >> t[i] >> P[i];
- Q.pb(mp(t[i],mp(P[i],i)));
- }
- sort(Q.begin(),Q.end());
- vector<pair<int,int>> v;
- bool used[n+1];
- for(int i = 0; i <= n; i++){
- used[i] = false;
- }
- for(int i = 0; i < n; i++){
- if(used[i])
- continue;
- int __r = nxt[i];
- if(i < n/2)
- __r = min(__r,n/2);
- for(int j = i; j < __r; j++) used[j] = 1;
- st.insert(a[i]);
- len[a[i]] = __r - i;
- upd(1,a[i],__r-i);
- }
- int cur_t = 1;
- bool all = false;
- for(auto& query : Q){
- int& t = query.first;
- int& pos = query.second.first;
- int& id = query.second.second;
- if(t == 0){
- ans[id] = a[pos-1];
- continue;
- }
- while(!all && cur_t < t){
- int y = getPos(1,1,n,n/2);
- auto it = st.lower_bound(y);
- it--;
- int x = *it;
- int tr = getSuff(y);
- if(n/2 - tr <= 0){
- all = true;
- break;
- }
- int delta = n/2 - tr;
- int __len = len[x];
- int __pos = rv[x] + __len - delta;
- upd(1,x,-delta);
- len[x] -= delta;
- while(__pos < rv[x] + __len){
- int __r = min(nxt[__pos],rv[x] + __len);
- st.insert(a[__pos]);
- upd(1,a[__pos],__r-__pos);
- len[a[__pos]] = __r - __pos;
- __pos = __r;
- }
- cur_t++;
- }
- int x = getPos(1,1,n,n-pos);
- auto it = st.lower_bound(x);
- it--;
- if(get(x,x) <= n-pos){
- x = *it;
- }
- int sz = len[x];
- int suffSum = 0;
- it = st.lower_bound(x);
- it++;
- if(it != st.end()){
- int y = *it;
- suffSum = getSuff(y);
- }
- int cur_pos = (n - pos + 1) - suffSum;
- cur_pos = sz - cur_pos;
- int __pos = rv[x];
- ans[id] = a[__pos + cur_pos];
- }
- for(int i = 0; i < q; i++){
- cout << ans[i] << "\n";
- }
- return;
- }
- signed main(){
- ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
- int tests = 1;
- // cin >> tests;
- for(int test = 1; test <= tests; test++){
- solve();
- }
- return 0;
- }
- /**
- **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement