oj.uz

Submission #772872

# Submission time Handle Problem Language Result Execution time Memory
772872 2023-07-04T12:06:48 Z doowey Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 24736 KB 
#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, treap, 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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 23052 KB Output is correct
2 Correct 215 ms 21816 KB Output is correct
3 Correct 233 ms 21444 KB Output is correct
4 Correct 201 ms 20432 KB Output is correct
5 Correct 224 ms 23596 KB Output is correct
6 Correct 199 ms 24064 KB Output is correct
7 Correct 219 ms 24736 KB Output is correct
8 Correct 200 ms 22716 KB Output is correct
9 Correct 199 ms 22016 KB Output is correct
10 Correct 208 ms 21448 KB Output is correct
11 Correct 207 ms 21916 KB Output is correct
12 Correct 197 ms 20208 KB Output is correct
13 Correct 203 ms 20880 KB Output is correct
14 Correct 207 ms 23188 KB Output is correct
15 Correct 208 ms 21588 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 206 ms 20208 KB Output is correct
18 Correct 195 ms 20180 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 22700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 12308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 23052 KB Output is correct
2 Correct 215 ms 21816 KB Output is correct
3 Correct 233 ms 21444 KB Output is correct
4 Correct 201 ms 20432 KB Output is correct
5 Correct 224 ms 23596 KB Output is correct
6 Correct 199 ms 24064 KB Output is correct
7 Correct 219 ms 24736 KB Output is correct
8 Correct 200 ms 22716 KB Output is correct
9 Correct 199 ms 22016 KB Output is correct
10 Correct 208 ms 21448 KB Output is correct
11 Correct 207 ms 21916 KB Output is correct
12 Correct 197 ms 20208 KB Output is correct
13 Correct 203 ms 20880 KB Output is correct
14 Correct 207 ms 23188 KB Output is correct
15 Correct 208 ms 21588 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 206 ms 20208 KB Output is correct
18 Correct 195 ms 20180 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Execution timed out 3053 ms 22700 KB Time limit exceeded
22 Halted 0 ms 0 KB -