oj.uz

Submission #772853

# Submission time Handle Problem Language Result Execution time Memory
772853 2023-07-04T11:56:11 Z doowey Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 26864 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(199);

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("in.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(res, res, sa);
            merge(res, 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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 26864 KB Output is correct
2 Correct 221 ms 23804 KB Output is correct
3 Correct 228 ms 23328 KB Output is correct
4 Correct 203 ms 22448 KB Output is correct
5 Correct 214 ms 25556 KB Output is correct
6 Correct 199 ms 25992 KB Output is correct
7 Correct 214 ms 26572 KB Output is correct
8 Correct 205 ms 24620 KB Output is correct
9 Correct 204 ms 23912 KB Output is correct
10 Correct 206 ms 23320 KB Output is correct
11 Correct 206 ms 23732 KB Output is correct
12 Correct 207 ms 22040 KB Output is correct
13 Correct 207 ms 22872 KB Output is correct
14 Correct 214 ms 25228 KB Output is correct
15 Correct 213 ms 23476 KB Output is correct
16 Correct 3 ms 5032 KB Output is correct
17 Correct 197 ms 22320 KB Output is correct
18 Correct 200 ms 22124 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 5032 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3037 ms 26580 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 3051 ms 13908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 26864 KB Output is correct
2 Correct 221 ms 23804 KB Output is correct
3 Correct 228 ms 23328 KB Output is correct
4 Correct 203 ms 22448 KB Output is correct
5 Correct 214 ms 25556 KB Output is correct
6 Correct 199 ms 25992 KB Output is correct
7 Correct 214 ms 26572 KB Output is correct
8 Correct 205 ms 24620 KB Output is correct
9 Correct 204 ms 23912 KB Output is correct
10 Correct 206 ms 23320 KB Output is correct
11 Correct 206 ms 23732 KB Output is correct
12 Correct 207 ms 22040 KB Output is correct
13 Correct 207 ms 22872 KB Output is correct
14 Correct 214 ms 25228 KB Output is correct
15 Correct 213 ms 23476 KB Output is correct
16 Correct 3 ms 5032 KB Output is correct
17 Correct 197 ms 22320 KB Output is correct
18 Correct 200 ms 22124 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 5032 KB Output is correct
21 Execution timed out 3037 ms 26580 KB Time limit exceeded
22 Halted 0 ms 0 KB -