#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int M = 1e6+2;
int n, m, bit, p[200002], dr[200002];
pair<int, int>interval[200002];
int aib[200002];
int ans[M];
struct queries{
int p, t, i;
bool operator < (const queries &other) {
return t < other.t;
}
} q[M];
void update (int x, int val) {
for (int i = x; i <= n; i += (i & -i)) {
aib[i] += val;
}
}
int query (int x) {
int s = 0;
for (int i = x; i; i -= (i & -i))
s += aib[i];
return s;
}
int binary (int x) {
int poz = 0;
int s = 0;
for (int i = (1 << bit); i; (i >>= 1)) {
if (poz + i <= n && s + aib[poz + i] < x) {
s += aib[poz + i];
poz += i;
}
}
return poz + 1;
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
for (int i = 1; i <= m; i++) {
cin >> q[i].t >> q[i].p;
q[i].i = i;
}
while ((1 << bit) <= n)
bit++;
bit--;
sort(q + 1,q + m + 1);
int ind = 1;
while (ind <= m && q[ind].t == 0) {
ans[q[ind].i] = p[q[ind].p];
ind++;
}
stack<int>st;
st.push(n + 1);
p[n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
while (p[st.top()] < p[i])
st.pop();
dr[i] = st.top();
st.push(i);
}
int j = 1;
while (j <= n) {
if (j <= n / 2) {
int l = j, r = min(n / 2, dr[j] - 1);
update(p[j], r - l + 1);
interval[p[j]] = {l, r};
j = r + 1;
}
else {
update(p[j], dr[j] - j);
interval[p[j]] = {j, dr[j] - 1};
j = dr[j];
}
}
int time = 0;
while (1) {
time++;
int val = binary(n / 2);
int sum = query(val);
while (ind <= m && q[ind].t == time) {
int poz = binary(q[ind].p);
int sum2 = query(poz - 1);
ans[q[ind].i] = p[interval[poz].first + q[ind].p - sum2 - 1];
ind++;
}
if (sum == n / 2)
break;
int overflow = sum - n / 2;
update(val, -overflow);
interval[val].second -= overflow;
int j = interval[val].second + 1;
while (j <= interval[val].second + overflow) {
update(p[j], dr[j] - j);
interval[p[j]] = {j, dr[j] - 1};
j = dr[j];
}
}
while (ind <= m) {
int poz = binary(q[ind].p);
int sum2 = query(poz - 1);
ans[q[ind].i] = p[interval[poz].first + q[ind].p - sum2 - 1];
ind++;
}
for (int i = 1; i <= m; i++)
cout << ans[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
298 ms |
20800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
382 ms |
32012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
5776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
298 ms |
20800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
