#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;
int n, q;
int niz[maxn];
int pos[maxn];
int t[maxn], p[maxn];
vector< int > qs[maxn];
int sol[maxn];
int tour[treesiz];
int l[maxn], r[maxn];
void update(int x, int val) {
x += off;
tour[x] = val;
x /= 2;
while (x > 0) tour[x] = tour[x * 2] + tour[x * 2 + 1], x /= 2;
}
int fin(int l, int r, int node, int val) {
if (l == r) return l;
int mid = (l + r) / 2;
if (tour[node * 2] >= val) return fin(l, mid, node * 2, val);
return fin(mid + 1, r, node * 2 + 1, val - tour[node * 2]);
}
int query(int a, int b, int l, int r, int node) {
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tour[node];
int mid = (l + r) / 2;
return query(a, b, l, mid, node * 2) + query(a, b, mid + 1, r, node * 2 + 1);
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++)
scanf("%d", niz+i);
for (int i = 0; i < q; i++) {
scanf("%d%d", t+i, p+i);
t[i] = min(t[i], n); p[i]--;
qs[t[i]].push_back(i);
}
niz[n] = inf;
stack< int > s; s.push(n);
for (int i = n - 1; i >= 0; i--) {
while (niz[s.top()] < niz[i]) s.pop();
pos[i] = s.top();
s.push(i);
}
for (int tren : qs[0]) sol[tren] = niz[p[tren]];
int ptr = 0;
memset(r, -1, sizeof r);
while (ptr < n) {
int val = niz[ptr];
l[val] = ptr;
r[val] = pos[ptr] - 1;
update(val, r[val] - l[val] + 1);
//printf("block: %d (%d %d)\n", val, l[val], r[val]);
ptr = pos[ptr];
}
update(n + 1, 100);
for (int ac = 1; ac <= n; ac++) {
int ind = fin(0, off - 1, 1, n / 2 + 1);
//printf("ind: %d\n", ind);
assert(query(1, n, 0, off - 1, 1) == n);
int prev = query(0, ind - 1, 0, off - 1, 1);
//printf("middle: %d --> %d\n", ind, prev);
if (prev != n / 2) {
int ptr = l[ind] + n / 2 - prev;
int cp = ptr;
//printf("ptr: %d\n", ptr);
while (ptr <= r[ind]) {
//printf("current ptr: %d\n", ptr);
int val = niz[ptr];
l[val] = ptr, r[val] = pos[ptr] - 1;
update(val, r[val] - l[val] + 1);
//printf("block: %d (%d %d)\n", val, l[val], r[val]);
ptr = pos[ptr];
}
r[ind] = cp - 1;
update(ind, r[ind] - l[ind] + 1);
}
for (int tren : qs[ac]) {
//printf("answering: %d\n", tren + 1);
int ind = fin(0, off - 1, 1, p[tren] + 1);
//assert(ind <= n);
//printf("in block: %d (%d %d)\n", ind, l[ind], r[ind]);
//assert(r[ind] - l[ind] >= 0);
int prev = query(0, ind - 1, 0, off - 1, 1);
//printf("prev size: %d\n", prev);
sol[tren] = niz[l[ind] + p[tren] - prev];
}
}
for (int i = 0; i < q; i++)
printf("%d\n", sol[i]);
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d", niz+i);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d%d", t+i, p+i);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
132 ms |
27976 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
150 ms |
24488 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
20840 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
132 ms |
27976 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
