#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#ifdef LOCAL
#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int N = 200200;
const int Q = 1000100;
int n, q;
int a[N];
int pos[N];
vector<pair<int, int>> Qs[N];
int ANS[Q];
int r[N];
set<int> setik;
struct Node {
int l, r, sum;
Node() : sum(0) {}
Node(int _l, int _r, int _sum) : l(_l), r(_r), sum(_sum) {}
};
const int M = (1 << 22);
Node tree[4 * M + 5];
Node merge(Node L, Node R) {
return Node(L.l, R.r, L.sum + R.sum);
}
void build(int v, int l, int r) {
tree[v] = Node(l, r, 0);
if (l == r) return;
int mid = l + r >> 1;
build(v * 2, l, mid);
build(v * 2 + 1, mid + 1, r);
}
void update(int p, int i, int v) {
if (tree[p].l > i || tree[p].r < i) return;
if (tree[p].l == tree[p].r) {
tree[p].sum = v;
return;
}
update(p * 2, i, v);
update(p * 2 + 1, i, v);
tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}
int getSum(int p, int r) {
if (tree[p].r <= r) return tree[p].sum;
if (tree[p].l > r) return 0;
return getSum(p * 2, r) + getSum(p * 2 + 1, r);
}
int getPos(int p, int v) {
// eprintf("segtree: %d %d %d\n", tree[p].l, tree[p].r, v);
int l = 0, r = M - 1, at = -1;
while (l <= r) {
int mid = l + r >> 1;
if (getSum(1, mid) < v)
at = mid, l = mid + 1;
else
r = mid - 1;
}
return at + 1;
}
void add(int x, int l) {
// eprintf("adding %d %d\n", x, l);
assert(setik.find(x) == setik.end());
setik.insert(x);
update(1, x, l);
}
void go(int i) {
i = pos[i];
// eprintf("OMFG GO FROM %d\n", i);
while(i <= n && setik.find(a[i]) == setik.end()) {
add(a[i], r[i] - i);
i = r[i];
}
}
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
pos[a[i]] = i;
}
vector<int> stk(1, n + 1);
for (int i = n; i >= 1; i--) {
while(stk.size() > 1 && a[stk.back()] <= a[i])
stk.pop_back();
r[i] = stk.back();
stk.push_back(i);
}
build(1, 0, M - 1);
go(a[1]);
for (int i = 0; i < q; i++) {
int t, x;
scanf("%d%d", &t, &x);
Qs[min(t, n + 1)].push_back(mp(x, i));
}
for (int i = 0; i <= n + 1; i++) {
for (auto& p : Qs[i]) {
int el = getPos(1, p.first);
// eprintf("p.first = %d el = %d\n", p.first, el);
// if (p.first == 5)
// eprintf("hIIIIIII sz = %d\n", setik.size());
ANS[p.second] = a[pos[el] + p.first - getSum(1, el - 1) - 1];
assert(ANS[p.second] <= el);
}
int id = getPos(1, n / 2 + 1);
assert(getSum(1, id) >= n / 2);
// eprintf("ID = %d\n", id);
if (getSum(1, id - 1) == n / 2)
continue;
int el = a[pos[id] + n / 2 - getSum(1, id - 1)];
int new_v = n / 2 - getSum(1, id - 1);
// eprintf("WTF %d %d and %d\n", id, new_v, el);
update(1, id, new_v);
go(el);
}
for (int i = 0; i < q; i++)
printf("%d\n", ANS[i]);
return 0;
}
Compilation message
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:79:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
79 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'int getPos(int, int)':
Main.cpp:102:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
102 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:131:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
131 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | scanf("%d%d", &t, &x);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1559 ms |
219728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1698 ms |
226008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
404 ms |
208524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1559 ms |
219728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
