#include <bits/stdc++.h>
using namespace std;
#define tol(bi) (1LL<<((int)(bi)))
#define int long long
struct SegTree{
vector<int> segtree;
SegTree(int n){
segtree.resize(n,0);
}
void update(int node, int x){
segtree[node]=x;
}
int query(int l, int r){
int ans = 0;
for (int i = l; i <= r; i++){
ans+=segtree[i];
}
return ans;
}
int find(int x){
int crr = 0;
for (int i = 0; i < segtree.size(); i++){
crr+=segtree[i];
if (crr>x) return i;
}
assert(false);
return 23;
}
};
int32_t 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],2*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 'long long int SegTree::find(long long int)':
Main.cpp:22:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (int i = 0; i < segtree.size(); i++){
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1987 ms |
35460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3031 ms |
37832 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3062 ms |
6484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1987 ms |
35460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
