oj.uz

답안 #772867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
772867 2023-07-04T12:03:56 Z doowey Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 25472 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 233 ms 24012 KB Output is correct
2 Correct 218 ms 22572 KB Output is correct
3 Correct 219 ms 22148 KB Output is correct
4 Correct 217 ms 21304 KB Output is correct
5 Correct 218 ms 24424 KB Output is correct
6 Correct 210 ms 24804 KB Output is correct
7 Correct 214 ms 25472 KB Output is correct
8 Correct 206 ms 23608 KB Output is correct
9 Correct 200 ms 22812 KB Output is correct
10 Correct 207 ms 22208 KB Output is correct
11 Correct 203 ms 22732 KB Output is correct
12 Correct 203 ms 20876 KB Output is correct
13 Correct 207 ms 21672 KB Output is correct
14 Correct 213 ms 24012 KB Output is correct
15 Correct 209 ms 22344 KB Output is correct
16 Correct 3 ms 5036 KB Output is correct
17 Correct 216 ms 21208 KB Output is correct
18 Correct 202 ms 20912 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

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 24012 KB Output is correct
2 Correct 218 ms 22572 KB Output is correct
3 Correct 219 ms 22148 KB Output is correct
4 Correct 217 ms 21304 KB Output is correct
5 Correct 218 ms 24424 KB Output is correct
6 Correct 210 ms 24804 KB Output is correct
7 Correct 214 ms 25472 KB Output is correct
8 Correct 206 ms 23608 KB Output is correct
9 Correct 200 ms 22812 KB Output is correct
10 Correct 207 ms 22208 KB Output is correct
11 Correct 203 ms 22732 KB Output is correct
12 Correct 203 ms 20876 KB Output is correct
13 Correct 207 ms 21672 KB Output is correct
14 Correct 213 ms 24012 KB Output is correct
15 Correct 209 ms 22344 KB Output is correct
16 Correct 3 ms 5036 KB Output is correct
17 Correct 216 ms 21208 KB Output is correct
18 Correct 202 ms 20912 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 3030 ms 23724 KB Time limit exceeded
22 Halted 0 ms 0 KB -