#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;
scanf("%d %d",&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];
scanf("%d %d",&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";
printf("%d\n",ans[i]);
}
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;
}
/**
**/
Compilation message
Main.cpp: In function 'void push(int, int, int)':
Main.cpp:21:9: warning: unused variable 'm' [-Wunused-variable]
21 | int m = (l+r)>>1;
| ^
Main.cpp: In function 'void solve()':
Main.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | scanf("%d %d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~
Main.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | scanf("%d %d",&t[i],&P[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
495 ms |
54564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
2160 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
