제출 #15792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15792		ainta	마상시합 토너먼트 (IOI12_tournament)	C++98	0 / 100	72 ms	5348 KiB

tournament

#include<stdio.h>
#include<algorithm>
#define Ptreap pair<treap *, treap *>
using namespace std;

int Res, RR, Ans;

struct treap{
    int key, pri, sz, d, g1, g2;
    treap *c1, *c2;
    treap(int key_, int d_, int g1_, int g2_){
        key = key_, sz = 1, d = d_, g1 = g1_, g2 = g2_;
        if(g1 <= RR){
            if(Res < d)Ans = key, Res = d;
        }
        c1 = c2 = NULL;
        pri = rand();
    }
    void setLeft(treap *nd){
        c1 = nd;
        CalcSize();
    }
    void setRight(treap *nd){
        c2 = nd;
        CalcSize();
    }
    void CalcSize(){
        sz = 1;
        if(c1) sz += c1->sz;
        if(c2) sz += c2->sz;
    }
};

Ptreap Divide(treap *root, int key){
    if(root == NULL)return Ptreap(NULL, NULL);
    if(root->key < key){
        Ptreap tp = Divide(root->c2, key);
        root->setRight(tp.first);
        return Ptreap(root, tp.second);
    }
    Ptreap tp = Divide(root->c1, key);
    root->setLeft(tp.second);
    return Ptreap(tp.first, root);
}

treap *Ins(treap *root, treap *nd){
    if(root == NULL)return nd;
    if(root->pri < nd->pri){
        Ptreap tp = Divide(root, nd->key);
        nd->setLeft(tp.first);
        nd->setRight(tp.second);
        return nd;
    }
    if(root->key < nd->key){
        root->setRight(Ins(root->c2, nd));
    }
    else{
        root->setLeft(Ins(root->c1, nd));
    }
    return root;
}

treap *Merge(treap *c1, treap *c2){
    if(c1 == NULL)return c2;
    if(c2 == NULL)return c1;
    if(c1->pri < c2->pri){
        c2->setLeft(Merge(c1, c2->c1));
        return c2;
    }
    c1->setRight(Merge(c1->c2, c2));
    return c1;
}

treap *Del(treap *root, int key){
    if(root->key == key)return Merge(root->c1, root->c2);
    if(root->key < key){
        root->setRight(Del(root->c2, key));
    }
    else{
        root->setLeft(Del(root->c1, key));
    }
    return root;
}

treap *OSRank(treap *root, int cnt){
    if(root->c1 && root->c1->sz >= cnt)return OSRank(root->c1, cnt);
    if(root->c1)cnt -= root->c1->sz;
    if(cnt==1)return root;
    return OSRank(root->c2,cnt-1);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    int i, j, d, g1, g2, key;
    treap *Root = NULL, *tp;
    Res = -1, RR = R;
    for(i=0;i<N - 1;i++){
        Root = Ins(Root, new treap(i, 0, -1, K[i]));
    }
    Root = Ins(Root, new treap(i, 0, -1, -1));
    for(i=0;i<C;i++){
        d=0,g1=g2=-1;
        for(j=0;j<=E[i]-S[i];j++){
            tp = OSRank(Root, S[i]+1);
            if(d < tp->d + 1){
                key = tp->key;
                d = tp->d + 1;
            }
            g1 = max(g1, tp->g1);
            if(j != E[i]-S[i])g1 = max(g1, tp->g2);
            else g2 = tp->g2;
            Root = Del(Root, tp->key);
        }
        Ins(Root, new treap(key, d, g1, g2));
    }
    return Ans;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51