#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int gen(int m){
return ((int)rng() % m + m) % m;
}
struct node{
int cnt;
int maxi;
int key;
int prior;
node *left;
node *right;
node(int val) : cnt(1), maxi(val), key(val), prior(gen((int)1e9)), left(NULL), right(NULL) {};
};
typedef node* pnode;
int get_cnt(pnode x){
if(!x) return 0;
return x->cnt;
}
int get_max(pnode x){
if(!x) return 0;
return x->maxi;
}
void update(pnode &t){
if(!t) return;
t->cnt = get_cnt(t->left) + 1 + get_cnt(t->right);
t->maxi = max({get_max(t->left), t->key, get_max(t->right)});
}
void split_by_size(pnode T, int key, pnode &lef, pnode &rig){
if(!T){
lef=rig=NULL;
return;
}
int id = get_cnt(T->left) + 1;
if(id <= key){
split_by_size(T->right, key-id, T->right, rig);
lef = T;
}
else{
split_by_size(T->left, key, lef, T->left);
rig = T;
}
update(T);
}
void split_by_max(pnode T, int key, pnode &lef, pnode &rig){
if(!T){
lef=rig=NULL;
return;
}
int id = max(get_max(T->left), T->key);
if(id < key){
split_by_max(T->right, key, T->right, rig);
lef = T;
}
else{
split_by_max(T->left, key, lef, T->left);
rig = T;
}
update(T);
}
void merge(pnode &T, pnode L, pnode R){ // assume keys in L are strictly smaller than R
if(!L && !R){
T = NULL;
return;
}
if(!L){
T = R;
return;
}
if(!R){
T = L;
return;
}
if((L -> prior) > (R -> prior)){
merge(L -> right, L -> right, R);
T = L;
}
else{
merge(R -> left, L, R -> left);
T = R;
}
update(T);
}
int get_id(pnode T, int idx){
if(!T) return -1;
int id = get_cnt(T->left) + 1;
if(id == idx){
return T->key;
}
else if(id < idx){
return get_id(T->right, idx-id);
}
else{
return get_id(T->left, idx);
}
}
const int N = (int)2e5 + 10;
const int M = (int)1e6 + 10;
vector<pii> qq[N];
int res[M];
int main(){
fastIO;
//freopen("test.txt", "r", stdin);
int n, q;
cin >> n >> q;
pnode treap = NULL;
int p;
for(int i = 0 ; i < n; i ++ ){
cin >> p;
merge(treap, treap, new node(p));
}
int t, ii;
for(int iq = 1; iq <= q; iq ++ ){
cin >> t >> ii;
t=min(t,n);
qq[t].push_back(mp(iq, ii));
}
int take;
for(int it = 0; it <= n; it ++ ){
if(it > 0){
pnode sa, sb;
split_by_size(treap, n / 2, sa, sb);
pnode res = NULL;
while(sb != NULL && sa != NULL){
take = get_id(sb, 1);
pnode c, d;
if(take < sa->maxi){
split_by_max(sa, take, c, sa);
split_by_size(sb, 1, d, sb);
merge(res, res, c);
merge(res, res, d);
}
else{
break;
}
}
merge(treap, res, sa);
merge(treap, res, sb);
//treap = res;
}
for(auto x : qq[it]){
res[x.fi] = get_id(treap, x.se);
}
}
for(int iq = 1; iq <= q; iq ++ ){
cout << res[iq] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
204 ms |
22576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3076 ms |
22708 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3067 ms |
12140 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
204 ms |
22576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
