#include <bits/stdc++.h>
using namespace std;
#define tol(bi) (1LL<<((int)(bi)))
struct SegTree{
vector<int> segtree;
SegTree(int n){
segtree.resize(tol(ceil(log2(n)+1))-1,0);
}
void update(int node, int x){
node+=segtree.size()/2;
segtree[node]=x;
while (node){
node=(node-1)/2;
segtree[node]=segtree[node*2+1]+segtree[node*2+2];
}
}
int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
if (l>=tarl && r<=tarr) return segtree[node];
if (l>tarr || r<tarl) return 0;
int mid = l+(r-l)/2;
int lnode = query(tarl, tarr, l, mid, node*2+1);
int rnode = query(tarl, tarr, mid+1, r, node*2+2);
return lnode+rnode;
}
int find(int x){
int node = 0;
while (node*2+1<segtree.size()){
if (segtree[node*2+1]<=x){
x-=segtree[node*2+1];
node=node*2+2;
}
else {
node=node*2+1;
}
}
return node-segtree.size()/2;
}
};
int main(){
int n,q;
cin>>n>>q;
vector<int> arr(n);
for (int i = 0; i < n; i++){
cin>>arr[i];
}
vector<int> bendensonra(n,n);
vector<int> stk;
vector<int> posses(n+1);
for (int i = n-1; i >= 0; i--){
posses[arr[i]]=i;
while (stk.size() && arr[stk.back()]<arr[i]) stk.pop_back();
if (stk.size()) bendensonra[i]=stk.back();
stk.push_back(i);
}
vector<array<int,3>> qarr(q);
for (int i = 0; i < q; ++i)
{
cin>>qarr[i][0]>>qarr[i][1];
qarr[i][2]=i;
}
sort(qarr.begin(), qarr.end());
int time = 0;
SegTree segtree(n+1);
int _pp = 0;
while (_pp<n){
int nex = bendensonra[_pp];
segtree.update(arr[_pp],nex-_pp);
_pp=nex;
}
vector<int> ansarr(q);
for (int i = 0; i < q; i++){
while (time<min(qarr[i][0],n)){
int ele = segtree.find(n/2);
int pos = posses[ele]+n/2-segtree.query(0,ele-1);
if (pos!=posses[ele]){
segtree.update(ele,pos-posses[ele]);
}
while (pos<n && segtree.query(arr[pos],arr[pos])==0){
int nex = bendensonra[pos];
segtree.update(arr[pos],nex-pos);
pos=nex;
}
time++;
}
int ele = segtree.find((qarr[i][1]-1));
int pos = posses[ele]+(qarr[i][1]-1)-segtree.query(0,ele-1);
ansarr[qarr[i][2]]=arr[pos];
}
for (int i = 0; i < q; ++i)
{
cout<<ansarr[i]<<endl;
}
}
Compilation message
Main.cpp: In member function 'int SegTree::find(int)':
Main.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | while (node*2+1<segtree.size()){
| ~~~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1610 ms |
27436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1841 ms |
40272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
218 ms |
6232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1610 ms |
27436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
