oj.uz

답안 #772870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
772870 2023-07-04T12:06:11 Z doowey Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 3000 ms 22708 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, 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 204 ms 22576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 204 ms 22576 KB Output isn't correct
2 Halted 0 ms 0 KB -