#include<bits/stdc++.h>
#define endl '\n'
#define de(x) cout << #x << " = " << x << endl;
#define all(A) A.begin(), A.end()
using namespace std;
const int MAXN = 2e5;
const int MAXQ = 1e6;
ostream& operator<<(ostream& out, array<int, 3> v){
out << "(" << v[0] << " " << v[1] << " " << v[2] << ")";
return out;
}
struct Treap{
struct Node{
array<int, 3> val;
int my_size, acc_size;
int prior;
Node *lc, *rc;
Node() {}
Node(array<int, 3> val) : val(val), prior(rand()), lc(nullptr), rc(nullptr), my_size(val[2] - val[1] + 1), acc_size(val[2] - val[1] + 1) {}
void update(){
acc_size = my_size + (lc == nullptr ? 0 : lc -> acc_size) + (rc == nullptr ? 0 : rc -> acc_size);
}
};
Node* root;
pair<Node*, Node*> split(Node* node, array<int, 3> key){
if(node == nullptr) return {nullptr, nullptr};
if(node -> val <= key){
auto [lt, rt] = split(node -> rc, key);
node -> rc = lt;
node -> update();
return {node, rt};
}
else{
auto [lt, rt] = split(node -> lc, key);
node -> lc = rt;
node -> update();
return {lt, node};
}
}
Node* merge(Node* lt, Node* rt){
if(lt == nullptr) return rt;
if(rt == nullptr) return lt;
if(lt -> prior < rt -> prior){
rt -> lc = merge(lt, rt -> lc);
rt -> update();
return rt;
}
else{
lt -> rc = merge(lt -> rc, rt);
lt -> update();
return lt;
}
}
void insert(array<int, 3> key){
auto [lt, rt] = split(root, key);
auto mt = new Node(key);
root = merge(merge(lt, mt), rt);
}
void erase(array<int, 3> low_key, array<int, 3> high_key){
auto [lt, mrt] = split(root, low_key);
auto [mt, rt] = split(mrt, high_key);
root = merge(lt, rt);
}
void util_print(Node* node){
if(node == nullptr) return;
util_print(node -> lc);
cout << node -> val << " ";
util_print(node -> rc);
}
void print(){ util_print(root); cout << endl; }
array<int, 3> util_search(Node* node, int &to_left, int key){
if(to_left + (node -> lc == nullptr ? 0 : node -> lc -> acc_size) < key && to_left + (node -> lc == nullptr ? 0 : node -> lc -> acc_size) + (node -> my_size) >= key){
to_left += (node -> lc == nullptr ? 0 : node -> lc -> acc_size);
return node -> val;
}
else if(to_left + (node -> lc == nullptr ? 0 : node -> lc -> acc_size) < key){
to_left += (node -> acc_size) - (node -> rc -> acc_size);
return util_search(node -> rc, to_left, key);
}
else{
return util_search(node -> lc, to_left, key);
}
}
pair<int, array<int, 3>> search(int key){
int shift = 0;
auto ret = util_search(root, shift, key);
return {shift, ret};
}
};
int n, q, a[MAXN + 5], ans[MAXQ + 5], nxt[MAXN + 5];
vector<array<int, 3>> queries;
Treap tr;
bool riffle_shuffle(){
auto [shift, block] = tr.search(n / 2);
if(shift + block[2] - block[1] + 1 == n / 2) return false;
auto [v, l, r] = block;
tr.erase({v, 0, 0}, {v + 1, 0, 0});
tr.insert({v, l, n / 2 - shift + block[1] - 1});
int m = n / 2 - shift + block[1];
while(m > 0 && m <= r){
tr.insert({a[m], m, nxt[m] - 1});
m = nxt[m];
}
return true;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> q;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
for(int i = 1; i <= n; ){
int j = i;
while(j <= n && a[j] <= a[i]){
++ j;
}
tr.insert({a[i], i, j - 1});
i = j;
}
stack<int> st;
for(int i = n; i >= 1; i --){
while(!st.empty() && a[st.top()] < a[i]){
st.pop();
}
nxt[i] = (st.empty() ? n+1 : st.top());
st.push(i);
}
for(int i = 0; i < q; i ++){
int x, t; cin >> t >> x;
queries.push_back({t, x, i});
}
sort(all(queries));
int cur_time = 0;
for(auto [t, x, idx] : queries){
while(cur_time < t){
if(riffle_shuffle()) ++ cur_time;
else cur_time = t;
}
auto [shift, block] = tr.search(x);
ans[idx] = a[x - shift + block[1] - 1];
}
for(int i = 0; i < q; i ++){
cout << ans[i] << endl;
}
}
/*
6 3
1 5 6 2 3 4
1 2
0 4
1 5
*/
Compilation message
Main.cpp: In constructor 'Treap::Node::Node(std::array<int, 3>)':
Main.cpp:20:14: warning: 'Treap::Node::rc' will be initialized after [-Wreorder]
20 | Node *lc, *rc;
| ^~
Main.cpp:18:7: warning: 'int Treap::Node::my_size' [-Wreorder]
18 | int my_size, acc_size;
| ^~~~~~~
Main.cpp:22:3: warning: when initialized here [-Wreorder]
22 | Node(array<int, 3> val) : val(val), prior(rand()), lc(nullptr), rc(nullptr), my_size(val[2] - val[1] + 1), acc_size(val[2] - val[1] + 1) {}
| ^~~~
Main.cpp: In member function 'std::pair<Treap::Node*, Treap::Node*> Treap::split(Treap::Node*, std::array<int, 3>)':
Main.cpp:31:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | auto [lt, rt] = split(node -> rc, key);
| ^
Main.cpp:37:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
37 | auto [lt, rt] = split(node -> lc, key);
| ^
Main.cpp: In member function 'void Treap::insert(std::array<int, 3>)':
Main.cpp:58:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | auto [lt, rt] = split(root, key);
| ^
Main.cpp: In member function 'void Treap::erase(std::array<int, 3>, std::array<int, 3>)':
Main.cpp:63:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | auto [lt, mrt] = split(root, low_key);
| ^
Main.cpp:64:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
64 | auto [mt, rt] = split(mrt, high_key);
| ^
Main.cpp: In function 'bool riffle_shuffle()':
Main.cpp:99:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
99 | auto [shift, block] = tr.search(n / 2);
| ^
Main.cpp:101:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
101 | auto [v, l, r] = block;
| ^
Main.cpp: In function 'int main()':
Main.cpp:142:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
142 | for(auto [t, x, idx] : queries){
| ^
Main.cpp:147:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
147 | auto [shift, block] = tr.search(x);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
257 ms |
28036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
304 ms |
46512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
10956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
257 ms |
28036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
