#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){
int nx = nxt[no];
auto lol = s.lower_bound(no);
if(lol!=s.end()){
nx = min(nx,(*lol));
}
s.insert(no);
add(arr[no],nx-no);
no = nx;
}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 |
Correct |
1445 ms |
26264 KB |
Output is correct |
2 |
Correct |
1401 ms |
27400 KB |
Output is correct |
3 |
Correct |
1331 ms |
26596 KB |
Output is correct |
4 |
Correct |
1316 ms |
25512 KB |
Output is correct |
5 |
Correct |
1413 ms |
27156 KB |
Output is correct |
6 |
Correct |
1321 ms |
25484 KB |
Output is correct |
7 |
Correct |
1401 ms |
27196 KB |
Output is correct |
8 |
Correct |
1317 ms |
25960 KB |
Output is correct |
9 |
Correct |
1307 ms |
25492 KB |
Output is correct |
10 |
Correct |
1330 ms |
25776 KB |
Output is correct |
11 |
Correct |
1340 ms |
26288 KB |
Output is correct |
12 |
Correct |
1314 ms |
24956 KB |
Output is correct |
13 |
Correct |
1373 ms |
26748 KB |
Output is correct |
14 |
Correct |
1347 ms |
26456 KB |
Output is correct |
15 |
Correct |
1390 ms |
26904 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1307 ms |
25300 KB |
Output is correct |
18 |
Correct |
1309 ms |
24748 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
16 ms |
6748 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
10180 KB |
Output is correct |
2 |
Correct |
211 ms |
10820 KB |
Output is correct |
3 |
Correct |
199 ms |
10328 KB |
Output is correct |
4 |
Correct |
182 ms |
6088 KB |
Output is correct |
5 |
Correct |
190 ms |
7764 KB |
Output is correct |
6 |
Correct |
169 ms |
6232 KB |
Output is correct |
7 |
Correct |
185 ms |
7112 KB |
Output is correct |
8 |
Correct |
166 ms |
6596 KB |
Output is correct |
9 |
Correct |
177 ms |
7288 KB |
Output is correct |
10 |
Correct |
171 ms |
5576 KB |
Output is correct |
11 |
Correct |
158 ms |
5768 KB |
Output is correct |
12 |
Correct |
159 ms |
5576 KB |
Output is correct |
13 |
Correct |
173 ms |
5900 KB |
Output is correct |
14 |
Correct |
161 ms |
5576 KB |
Output is correct |
15 |
Correct |
162 ms |
5596 KB |
Output is correct |
16 |
Correct |
9 ms |
2648 KB |
Output is correct |
17 |
Correct |
183 ms |
10492 KB |
Output is correct |
18 |
Correct |
152 ms |
4944 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1445 ms |
26264 KB |
Output is correct |
2 |
Correct |
1401 ms |
27400 KB |
Output is correct |
3 |
Correct |
1331 ms |
26596 KB |
Output is correct |
4 |
Correct |
1316 ms |
25512 KB |
Output is correct |
5 |
Correct |
1413 ms |
27156 KB |
Output is correct |
6 |
Correct |
1321 ms |
25484 KB |
Output is correct |
7 |
Correct |
1401 ms |
27196 KB |
Output is correct |
8 |
Correct |
1317 ms |
25960 KB |
Output is correct |
9 |
Correct |
1307 ms |
25492 KB |
Output is correct |
10 |
Correct |
1330 ms |
25776 KB |
Output is correct |
11 |
Correct |
1340 ms |
26288 KB |
Output is correct |
12 |
Correct |
1314 ms |
24956 KB |
Output is correct |
13 |
Correct |
1373 ms |
26748 KB |
Output is correct |
14 |
Correct |
1347 ms |
26456 KB |
Output is correct |
15 |
Correct |
1390 ms |
26904 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1307 ms |
25300 KB |
Output is correct |
18 |
Correct |
1309 ms |
24748 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Runtime error |
16 ms |
6748 KB |
Execution killed with signal 11 |
22 |
Halted |
0 ms |
0 KB |
- |