#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
const int NMAX = 2e5;
const int QMAX = 1e6;
int n, q;
int a[NMAX + 2];
pair<int, int> qr[QMAX + 1];
int ans[QMAX + 1];
vector<int> idQ[NMAX + 1];
int nxt[NMAX + 2];
void read() {
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
a[n + 1] = n + 1;
for (int i = 1; i <= q; i++) {
cin >> qr[i].first >> qr[i].second;
qr[i].first = min(qr[i].first, n - 1);
idQ[qr[i].first].push_back(i);
}
}
struct Block {
int v, l, r;
bool operator < (const Block & oth) const {
return v < oth.v;
}
};
set<Block> s;
vector<Block> vtot;
map<Block, int> mp;
namespace AIB {
int aib[2 * NMAX + 1];
int m = 2 * n;
int query(int pos) {
int res = 0;
for (; pos > 0; pos -= pos & -pos)
res += aib[pos];
return res;
}
void update(int pos, int v) {
for (; pos <= m; pos += pos & -pos)
aib[pos] += v;
}
int get_block(int pos) {
int idx = 0, s = 0;
for (int b = 18; b >= 0; b--) {
if (idx + (1 << b) <= m && s + aib[idx + (1 << b)] < pos) {
s += aib[idx + (1 << b)];
idx += (1 << b);
}
}
return idx + 1;
}
void init(int _m) {
m = _m;
}
}
void adauga(Block b) {
s.insert(b);
AIB::update(mp[b], + (b.r - b.l + 1));
}
void scoate(Block b) {
s.erase(b);
AIB::update(mp[b], - (b.r - b.l + 1));
}
void solve() {
stack<int> stk;
stk.push(n + 1);
for (int i = n; i >= 1; i--) {
while (a[stk.top()] < a[i]) stk.pop();
nxt[i] = stk.top();
stk.push(i);
}
for (int st = 1; st <= n; st = nxt[st]) {
s.insert({a[st], st, nxt[st] - 1});
vtot.push_back({a[st], st, nxt[st] - 1});
}
int ltotal = n;
for (int step = 0; step <= n - 1; step++) {
while (true) {
auto it = prev(s.end());
if (ltotal - (it->r - it->l) > n / 2) {
ltotal -= (it->r - it->l + 1);
s.erase(it);
} else break;
}
if (ltotal > n / 2) {
auto ult = prev(s.end());
int L = ult->l, R = ult->r, V = ult->v;
s.erase(ult);
int lgR = ltotal - n / 2;
int lgL = R - L + 1 - lgR;
int v1 = V;
int l1 = L;
int r1 = L + lgL - 1;
s.insert({v1, l1, r1});
vtot.push_back({v1, l1, r1});
int l2 = r1 + 1;
int r2 = l2 + lgR - 1;
for (int idx = l2; idx <= r2; idx = nxt[idx]) {
s.insert({a[idx], idx, nxt[idx] - 1});
vtot.push_back({a[idx], idx, nxt[idx] - 1});
}
}
}
sort(vtot.begin(), vtot.end());
int cnt = vtot.size();
for (int i = 0; i < cnt; i++) {
mp[vtot[i]] = i + 1;
}
s.clear();
ltotal = n;
AIB::init(cnt);
for (int st = 1; st <= n; st = nxt[st]) {
adauga({a[st], st, nxt[st] - 1});
}
ltotal = n;
for (int step = 0; step <= n - 1; step++) {
for (int idxQ : idQ[step]) {
int pos = qr[idxQ].second;
int t = AIB::get_block(pos);
ans[idxQ] = a[vtot[t - 1].l + pos - AIB::query(t - 1) - 1];
}
while (true) {
auto it = prev(s.end());
if (ltotal - (it->r - it->l) > n / 2) {
ltotal -= (it->r - it->l + 1);
s.erase(*it);
//scoate(*it);
} else break;
}
if (ltotal > n / 2) {
auto ult = prev(s.end());
int L = ult->l, R = ult->r, V = ult->v;
scoate(*ult);
int lgR = ltotal - n / 2;
int lgL = R - L + 1 - lgR;
int v1 = V;
int l1 = L;
int r1 = L + lgL - 1;
adauga({v1, l1, r1});
int l2 = r1 + 1;
int r2 = l2 + lgR - 1;
for (int idx = l2; idx <= r2; idx = nxt[idx]) {
adauga({a[idx], idx, nxt[idx] - 1});
}
}
}
}
void write() {
for (int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
read();
solve();
write();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
33340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
457 ms |
65168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
23488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
33340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
