#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#endif
int n;
int bit[100001];
void add(int e,int v){
while(e<=n){
bit[e]+=v;
e+=e&-e;
}
}
int sum(int e){
int su = 0;
while(e>=1){
su+=bit[e];
e-=e&-e;
}
return su;
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int q;
cin>>n>>q;
int arr[n+1],pos[n+1];
for(int i = 1;i<=n;i++){
cin>>arr[i];
pos[arr[i]] = i;
}
int nxt[n+1];
stack<int> st;
for(int i = n;i>=1;i--){
while(!st.empty()&&arr[i]>=arr[st.top()])st.pop();
if(st.size())nxt[i] = st.top();
else nxt[i] = n+1;
st.push(i);
}
int cur = 1;
set<int> s;
while(cur<=n){
s.insert(cur);
add(arr[cur],nxt[cur]-cur);
cur = nxt[cur];
}
std::vector<array<int,3>> qu;
for(int i = 1;i<=q;i++){
int a,b;
cin>>a>>b;
a = min(a,n);
qu.push_back({a,b,i});
}sort(qu.begin(),qu.end());
int level = 0;
int ANS[q+1];
for(int i = 0;i<qu.size();i++){
while(level<qu[i][0]){
int no = n/2+1;
int l = 1 , r = n , ans = 0;
while(l<=r){
int mid = (l+r)/2;
if(sum(mid)>=no){
ans = mid;
r = mid-1;
}else l = mid+1;
}
int po = pos[ans]+(no-sum(ans-1)-1);
no = po;
auto it = s.lower_bound(no);
int en = n+1;
if(it!=s.end()){
en = (*it);
}
if(it==s.end()||(*it)!=no){
it--;
add(arr[(*it)],(-(en-(*it))) +(no-(*it)));
}
while(no<=n){
auto it = s.lower_bound(no);
if(it==s.end()||(*it)!=no){
s.insert(no);
add(arr[no],nxt[no]-no);
no = nxt[no];
}else break;
}
level++;
}
int l = 1 , r = n , ans = 0;
while(l<=r){
int mid = (l+r)/2;
if(sum(mid)>=qu[i][1]){
ans = mid;
r = mid-1;
}else l = mid+1;
}
ANS[qu[i][2]] = arr[pos[ans]+(qu[i][1]-sum(ans-1)-1)];
}
for(int i = 1;i<=q;i++)cout<<ANS[i]<<endl;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 0;i<qu.size();i++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1419 ms |
26956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
6744 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
7880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1419 ms |
26956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
