#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 2e5 + 5, maxq = 1e6 + 5;
struct Data {
int v, l, r, id;
friend bool operator<(Data A, Data B) {
if(A.v != B.v)
return A.v < B.v;
return A.id < B.id;
}
int len() {return r - l + 1;}
};
int n, q, m;
int p[maxn];
int ID[maxn * 2];
int nxt[maxn];
int ans[maxq];
vector<ii> qs[maxn];
set<Data> active;
vector<Data> blocks;
struct Seg {
int pot;
vector<int> T;
void init(int sz) {
pot = 1;
while(pot < sz) pot <<= 1;
T = vector<int>((pot << 1), 0);
}
void update(int x, int v) {
x += pot;
T[x] = v, x >>= 1;
while(x > 0) T[x] = T[x * 2] + T[x * 2 + 1], x >>= 1;
}
ii query(int x, int lo, int hi, int cnt) {
if(lo == hi) return {x - pot, cnt};
int mid = (lo + hi) / 2;
if(T[x * 2] >= cnt)
return query(x * 2, lo, mid, cnt);
return query(x * 2 + 1, mid + 1, hi, cnt - T[x * 2]);
}
int get(int x) {
ii res = query(1, 0, pot - 1, x);
return p[blocks[res.x].l + res.y - 1];
}
} S;
void init() {
int x = 0, idx = 0;
while(x != n)
blocks.pb({p[x], x, nxt[x] - 1, idx++}), x = nxt[x];
}
void build() {
int sz = n, idx = (int)blocks.size();
for(Data D : blocks)
active.insert(D);
int flag = 1;
while(flag) {
while(1) {
auto it = --active.end();
int len = it->r - it->l + 1;
if(sz - len >= n / 2)
active.erase(it), sz -= len;
else break;
}
if(sz == n / 2) flag = 0;
else {
auto it = --active.end();
Data D = *it;
active.erase(it);
int nr = D.r - (sz - (n / 2)) + 1;
Data D1 = {D.v, D.l, nr - 1, idx++};
active.insert(D1), blocks.pb(D1);
while(nr <= D.r) {
Data Di = {p[nr], nr, nxt[nr] - 1, idx++};
active.insert(Di), blocks.pb(Di);
nr = nxt[nr];
}
}
}
m = (int)blocks.size();
sort(all(blocks));
for(int i = 0;i < m;i++)
ID[blocks[i].id] = i;
S.init(m);
}
void solve() {
int x = 0, idx = 0, sz = n;
active.clear();
while(x != n) {
S.update(ID[idx], nxt[x] - x);
active.insert({p[x], x, nxt[x] - 1, idx++});
x = nxt[x];
}
for(int t = 0;t <= n;t++) {
for(ii qi : qs[t])
ans[qi.y] = S.get(qi.x);
while(1) {
auto it = --active.end();
int len = it->r - it->l + 1;
if(sz - len >= n / 2)
active.erase(it), sz -= len;
else break;
}
if(sz > n / 2) {
auto it = --active.end();
Data D = *it;
active.erase(it);
S.update(ID[D.id], 0);
int nr = D.r - (sz - (n / 2)) + 1;
Data D1 = {D.v, D.l, nr - 1, idx++};
active.insert(D1);
S.update(ID[D1.id], D1.len());
while(nr <= D.r) {
Data Di = {p[nr], nr, nxt[nr] - 1, idx++};
active.insert(Di);
S.update(ID[Di.id], Di.len());
nr = nxt[nr];
}
}
}
}
int main() {
scanf("%d%d", &n, &q);
for(int i = 0;i < n;i++)
scanf("%d", p + i);
for(int i = 0;i < q;i++) {
int t, x;
scanf("%d%d", &t, &x);
qs[min(t, n)].pb({x, i});
}
p[n] = n + 1;
vector<int> v = {n};
for(int i = n - 1;i >= 0;i--) {
while(p[i] > p[v.back()]) v.pop_back();
nxt[i] = v.back(), v.pb(i);
}
init();
build();
memset(ans, -1, sizeof ans);
solve();
for(int i = 0;i < q;i++)
printf("%d\n", ans[i]);
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | scanf("%d", p + i);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | scanf("%d%d", &t, &x);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
240 ms |
30152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
354 ms |
54592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
105 ms |
23044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
240 ms |
30152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
