제출 #38878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38878		andy627	마상시합 토너먼트 (IOI12_tournament)	C++14	100 / 100	126 ms	8160 KiB

tournament

#include <algorithm>
using namespace std;

#define MAXN 100005
#define TS 262144

static int N,R,A[MAXN],EP[MAXN];
static int sumtree[TS],erased[TS],maxtree[TS],ST=TS/2-1;

static struct NODE{
    NODE(){}
    NODE(int mx,int mn): max_val(mx), min_pos(mn){ }
    int max_val,min_pos;
    bool operator < (const NODE &ot)const{
        return max_val!=ot.max_val?max_val<ot.max_val:min_pos>ot.min_pos;
    }
} tree[TS],ans(0,1);

int get_real_pos(int n,int l,int r,int p)
{
    int m=(l+r)>>1;
    if (l == r) return m;
    if (p <= sumtree[n+n]) return get_real_pos(n+n,l,m,p);
    return get_real_pos(n+n+1,m+1,r,p-sumtree[n+n]);
}

void erase(int n,int l,int r,int s,int e)
{
    if (r < s || l > e) return;
    if (s <= l && r <= e){
        erased[n] = 1;
        sumtree[n] = 0;
        return;
    }
    int m=(l+r)>>1;
    erase(n+n,l,m,s,e);
    erase(n+n+1,m+1,r,s,e);
    if (erased[n]) sumtree[n] = 0;
    else sumtree[n] = sumtree[n+n]+sumtree[n+n+1];
}

int get_max(int l,int r)
{
    int ret=0;
    for (;l<=r;l>>=1,r>>=1){
        if (l&1) ret = max(ret,maxtree[l++]);
        if (!(r&1)) ret = max(ret,maxtree[r--]);
    }
    return ret;
}

NODE get_max_node(int l,int r)
{
    NODE ret(-1e9,-1e9);
    for (;l<=r;l>>=1,r>>=1){
        if (l&1) ret = max(ret,tree[l++]);
        if (!(r&1)) ret = max(ret,tree[r--]);
    }
    return ret;
}

void set_node(int n,const NODE &val)
{
    for (;n;n>>=1) tree[n] = max(tree[n],val);
}

int GetBestPosition(int n, int C, int r, int *order, int *S, int *E)
{
    int i,s,e;
    N = n, R = ++r;
    for (i=0;i<N-1;i++) A[i+1] = ++order[i];
    for (i=1;i<=N;i++) sumtree[ST+i] = 1, EP[i] = i;
    for (i=ST;i;i--) sumtree[i] = sumtree[i+i]+sumtree[i+i+1];
    for (i=0;i<C;i++){
        ++S[i]; ++E[i];
        s = get_real_pos(1,1,TS>>1,S[i]);
        e = get_real_pos(1,1,TS>>1,E[i]); e = EP[e];
        S[i] = s; E[i] = e;
        erase(1,1,TS>>1,s+1,e);
        EP[s] = e;
    }
    for (i=1;i<N;i++) maxtree[ST+i] = A[i];
    for (i=ST;i;i--) maxtree[i] = max(maxtree[i+i],maxtree[i+i+1]);
    for (i=0;i<TS;i++) tree[i].max_val = -1e9;
    for (i=0;i<C;i++){
        if (get_max(ST+S[i],ST+E[i]-1) > R) continue;
        NODE me(1,S[i]),mx;
        mx = get_max_node(ST+S[i],ST+E[i]-1);
        mx.max_val++;
        if (me < mx) me = mx;
        set_node(ST+S[i],me);
        ans = max(ans,me);
    }
    return --ans.min_pos;
}

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