#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int) 2e5 + 7;
const int Q = (int) 1e6 + 7;
const int INF = (int) 1e9;
int a[N], sol[Q];
vector<pair<int, int>> questions[N];
int n, q;
mt19937 rng;
int gen() {
return uniform_int_distribution<int>(INF)(rng);
}
struct Node {
int val;
int sz;
int prio;
int mx;
Node* left;
Node* right;
Node(int val_ = 0) {
val = val_;
mx = val_;
sz = 1;
prio = gen();
left = NULL;
right = NULL;
}
};
struct Treap {
int getsize(Node* &root) {
if (root == NULL) {
return 0;
} else {
return root->sz;
}
}
int getmax(Node* &root) {
if (root == NULL) {
return 0;
} else {
return root->mx;
}
}
void computesize(Node* &root) {
root->sz = 1 + getsize(root->left) + getsize(root->right);
}
pair<Node*, Node*> split(Node* &root, int target) { /// dupa val
if (root == NULL) {
return {NULL, NULL};
} else if (root->val <= target) {
pair<Node*, Node*> sol = split(root->right, target);
root->right = sol.first;
computesize(root);
return {root, sol.second};
} else {
pair<Node*, Node*> sol = split(root->left, target);
root->left = sol.second;
computesize(root);
return {sol.first, root};
}
}
pair<Node*, Node*> splitSize(Node* &root, int target) { /// dupa size
if (root == NULL) {
return {NULL, NULL};
}
int cnt = getsize(root->left);
if (cnt <= target) {
pair<Node*, Node*> sol = splitSize(root->right, target - cnt);
root->right = sol.first;
computesize(root);
return {root, sol.second};
} else {
pair<Node*, Node*> sol = splitSize(root->left, target);
root->left = sol.second;
computesize(root);
return {sol.first, root};
}
}
Node* _merge(Node* &a, Node* &b) {
if (a == NULL && b == NULL) {
return NULL;
} else if (a == NULL) {
return b;
} else if (b == NULL) {
return a;
} else if (a->prio < b->prio) {
a->right = _merge(a->right, b);
computesize(a);
if (a != NULL) {
a->mx = max({a->val, getmax(a->left), getmax(a->right)});
}
return a;
} else {
b->left = _merge(a, b->left);
computesize(b);
if (b != NULL) {
b->mx = max({b->val, getmax(b->left), getmax(b->right)});
}
return b;
}
}
int _kth(Node* &root, int k) {
if (root == NULL) {
return -1;
}
int cnt = getsize(root->left) + 1;
if (cnt == k) {
return root->val;
} else if (cnt < k) {
return _kth(root->right, k - cnt);
} else {
return _kth(root->left, k);
}
}
Node* root;
Treap() {
root = NULL;
}
void _insert(int val) {
pair<Node*, Node*> sol = split(root, val);
Node* newnode = new Node(val);
sol.first = _merge(sol.first, newnode);
root = _merge(sol.first, sol.second);
}
int _query(int val) {
pair<Node*, Node*> sol = split(root, val - 1);
int ret = getsize(sol.second);
root = _merge(sol.first, sol.second);
return ret;
}
pair<Node*, Node*> extractSize(int target) {
return splitSize(root, target);
}
pair<Node*, Node*> extractMax(int target) {
return split(root, target);
}
void mergee(Node *aux) {
root = _merge(root, aux);
}
int kth(int x) {
return _kth(root, x);
}
void del() {
root = NULL;
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("input", "r", stdin);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= q; i++) {
int t, x;
cin >> t >> x;
questions[min(t, n)].push_back({x, i});
}
Treap t;
for (int i = 1; i <= n; i++) {
Node* aux;
aux = new Node(a[i]);
t.mergee(aux);
}
for (int lap = 0; lap <= n; lap++) {
if (lap != 0) {
Treap x, y;
pair<Node*, Node*> aux = t.extractSize(n / 2);
x.root = aux.first;
y.root = aux.second;
t.del();
while (x.root != NULL && y.root != NULL) {
int vv = y.kth(1);
Treap z, zz;
if (vv < x.root->mx) {
pair<Node*, Node*> aux = x.extractMax(vv);
z.root = aux.first;
x.root = aux.second;
int big = INF;
if (y.root != NULL) {
big = x.kth(1);
}
aux = y.extractMax(big);
zz.root = aux.first;
y.root = aux.second;
t.mergee(z.root);
t.mergee(zz.root);
} else {
break;
}
}
t.mergee(x.root);
t.mergee(y.root);
}
for (auto &it : questions[lap]) {
sol[it.second] = t.kth(it.first);
}
}
for (int i = 1; i <= q; i++) {
cout << sol[i] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
249 ms |
23056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
378 ms |
33352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
111 ms |
13204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
249 ms |
23056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
