#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 240;
const int INF = 1e9 + 7;
const int BASE = 137;
struct fenwick_Tree {
int m;
int fen[N];
void init (int n) {
m = n;
}
void update (int pos, int val) {
for (;pos <= m; pos += pos & -pos) fen[pos] += val;
}
int get (int pos) {
int res = 0;
for (;pos > 0; pos -= pos & -pos) res += fen[pos];
return res;
}
}fen;
int n, Q;
int a[N];
pair<int,int> itv[N];
vector<pair<int,int>> qr[N];
int spt[N][25];
int Ans[N];
void solution () {
cin >> n >> Q;
rep (i, 1, n) cin >> a[i];
fen.init(n);
rep (i, 1, n) spt[i][0] = a[i];
for (int j = 1; (1 << j) <= n; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
spt[i][j] = max(spt[i][j - 1], spt[i + (1 << j - 1)][j - 1]);
auto get = [] (int L, int R) {
assert(L <= R);
int K = 31 - __builtin_clz(R - L + 1);
return max(spt[L][K], spt[R - (1 << K) + 1][K]);
};
auto get_bound = [&] (int pos) {
int lf = pos, rt = n;
while (lf < rt) {
int mid = lf + rt + 1 >> 1;
if (get(pos, mid) == a[pos]) lf = mid;
else rt = mid - 1;
}
return lf;
};
rep (i, 1, n) {
int bound = get_bound(i);
itv[a[i]] = {i, bound};
fen.update (a[i], bound - i + 1);
i = bound;
}
rep (i, 1, Q) {
int T, p;
cin >> T >> p;
T = min(T, n);
qr[T].push_back({p, i});
}
auto get_val = [] (int p) {
int lf = 1, rt = n;
while (lf < rt) {
int mid = lf + rt >> 1;
if (fen.get(mid) >= p) rt = mid;
else lf = mid + 1;
}
return lf;
};
auto simulation = [&] (int p) {
int val = get_val(p);
int L = itv[val].fs, R = itv[val].se;
// cout << val <<"hihi\n";
if (p - fen.get(val - 1) == 1)
return;
int np = L + p - fen.get(val - 1) - 1;
// cout << np <<" aa\n";
fen.update(val, - (R - np + 1));
itv[val] = {L, np - 1};
rep (i, np, R) {
int bound = get_bound(i);
itv[a[i]] = {i, bound};
fen.update(a[i], bound - i + 1);
i = bound;
}
};
rep (i, 0, n) {
// cout << i <<":\n";
// rep (i, 1, n) cout << a[i] <<" "<<itv[a[i]].fs<<" "<<itv[a[i]].se <<"\n";
iter (&id, qr[i]) {
int val = get_val(id.fs);
// cout << id.se <<" "<<id.fs<<" "<<val<<" "<<itv[val].fs<<" "<<itv[val].se<<" "<<fen.get(4)<<"qr\n";
Ans[id.se] = a[itv[val].fs + id.fs - fen.get(val - 1) - 1];
}
simulation(n/2 + 1);
}
rep (i, 1, Q) {
cout << Ans[i] <<"\n";
}
}
#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);
/*
*/
int main () {
// file("c");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
no bug challenge +2
6
25 18 40 37 29 95 41 53 39 69 61 90
14 18 22 28 18 30 32 32 63 58 71 78
*/
Compilation message
Main.cpp: In function 'void solution()':
Main.cpp:59:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
59 | spt[i][j] = max(spt[i][j - 1], spt[i + (1 << j - 1)][j - 1]);
| ~~^~~
Main.cpp: In lambda function:
Main.cpp:70:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int mid = lf + rt + 1 >> 1;
| ~~~~~~~~^~~
Main.cpp: In lambda function:
Main.cpp:94:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int mid = lf + rt >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
179 ms |
34184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
284 ms |
55988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
25940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
179 ms |
34184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
