#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200'005;
vector<array<int, 2>> ask[N];
int a[N], ans[1'000'005];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < q; i++) {
int t, p;
cin >> t >> p;
t = min(t, n);
ask[t].push_back({p - 1, i});
}
int nxt[n]{};
stack<int> st;
a[n] = 1e9;
st.push(n);
for (int i = n - 1; i >= 0; i--) {
while (a[i] > a[st.top()]) st.pop();
nxt[i] = st.top();
st.push(i);
}
set<array<int, 2>> s;
int cnt[n]{};
for (int i = 0; i < n; i = nxt[i]) {
cnt[i] = nxt[i] - i;
s.insert({a[i], i});
}
bool isover = 0;
for (int j = 0; j <= n; j++) {
for (auto [p, idx] : ask[j]) {
for (auto [v, i] : s) {
if (p < cnt[i]) {
ans[idx] = a[i + p];
break;
} else {
p -= cnt[i];
}
}
}
if (isover) continue;
int cur = n / 2;
for (auto [v, i] : s) {
if (cur < cnt[i]) {
if (cur == 0) {
isover = 1;
break;
}
cnt[i] = cur;
cur = i + cur;
while (cur < n && cnt[cur] == 0) {
cnt[cur] = nxt[cur] - cur;
s.insert({a[cur], cur});
cur = nxt[cur];
}
break;
} else {
cur -= cnt[i];
}
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
333 ms |
31200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
338 ms |
43628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1547 ms |
17332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
333 ms |
31200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
