oj.uz

답안 #772864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
772864 2023-07-04T12:00:56 Z doowey Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 25424 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(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

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 24220 KB Output is correct
2 Correct 217 ms 22560 KB Output is correct
3 Correct 222 ms 22216 KB Output is correct
4 Correct 201 ms 21300 KB Output is correct
5 Correct 216 ms 24404 KB Output is correct
6 Correct 200 ms 24896 KB Output is correct
7 Correct 221 ms 25424 KB Output is correct
8 Correct 200 ms 23488 KB Output is correct
9 Correct 205 ms 22844 KB Output is correct
10 Correct 207 ms 22224 KB Output is correct
11 Correct 210 ms 22860 KB Output is correct
12 Correct 197 ms 20880 KB Output is correct
13 Correct 210 ms 21748 KB Output is correct
14 Correct 209 ms 23940 KB Output is correct
15 Correct 223 ms 22432 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 202 ms 21096 KB Output is correct
18 Correct 202 ms 20948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3051 ms 23844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3032 ms 12492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 24220 KB Output is correct
2 Correct 217 ms 22560 KB Output is correct
3 Correct 222 ms 22216 KB Output is correct
4 Correct 201 ms 21300 KB Output is correct
5 Correct 216 ms 24404 KB Output is correct
6 Correct 200 ms 24896 KB Output is correct
7 Correct 221 ms 25424 KB Output is correct
8 Correct 200 ms 23488 KB Output is correct
9 Correct 205 ms 22844 KB Output is correct
10 Correct 207 ms 22224 KB Output is correct
11 Correct 210 ms 22860 KB Output is correct
12 Correct 197 ms 20880 KB Output is correct
13 Correct 210 ms 21748 KB Output is correct
14 Correct 209 ms 23940 KB Output is correct
15 Correct 223 ms 22432 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 202 ms 21096 KB Output is correct
18 Correct 202 ms 20948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Execution timed out 3051 ms 23844 KB Time limit exceeded
22 Halted 0 ms 0 KB -