Submission #845

#	Time	Username	Problem	Language	Result	Execution time	Memory
845		tncks0121	Jousting tournament (IOI12_tournament)	C++98	100 / 100	72 ms	6192 KiB

tournament

#include <algorithm>
 
int *Sum;
int *Tree; int TS;
int *Stk; int tp;
 
struct Intv{
    int st, en;
    Intv(){ st = en = 0; }
    bool operator< (const Intv &t) const{
        if(st != t.st) return st < t.st;
        return en > t.en;
    }
} *Interval;
 
int FindPos(int pos){
    int nd = 1, width = TS;
    while(nd < TS){
        width >>= 1;
        if(width - Tree[nd * 2] >= pos) nd = nd * 2;
        else pos -= width - Tree[nd * 2], nd = nd * 2 + 1;
    }
    return nd - TS + 1;
}
 
bool intersect(Intv a, Intv b){
    return (a.st <= b.st && b.en <= a.en);
}
 
int* change, cn;
 
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
    int i, j;
 
    Sum = (int*) calloc((N + 1), sizeof(int)); Sum[0] = 0;
    for(i = 1; i < N; ++i) Sum[i] = Sum[i-1] + (K[i-1] > R);
 
    for(TS = 1; TS < N; TS <<= 1); TS <<= 1;
    Tree = (int*) calloc((TS * 2 + 1), sizeof(int));
    Interval = (Intv*) calloc(C, sizeof(Intv));
    change = (int*) calloc(N + 1, sizeof(int));
 
    for(i = 0; i < C; ++i){
        int s = S[i] + 1, e = E[i] + 1; cn = 0;
        Interval[i].st = FindPos(s);
        Interval[i].en = FindPos(e + 1) - 1;
        for(j = s + 1; j <= e; j++) change[++cn] = FindPos(j);
        for(j = 1; j <= cn; j++) if(!Tree[change[j] + TS - 1]){
            for(int t = change[j] + TS - 1; t > 0; t>>=1) ++Tree[t];
        }
    }
 
    Stk = (int*) calloc(C, sizeof(int)); tp = 0;
    std::sort(Interval, Interval + C);
    int maxdepth = 0, ret = 0;
    for(i = 0; i < C; ++i){
        while(tp > 0 && !intersect(Interval[Stk[tp]], Interval[i])) --tp;
        if(Sum[Interval[i].en - 1] == Sum[Interval[i].st - 1]) Stk[++tp] = i;
        if(tp > maxdepth){
            maxdepth = tp; 
            ret = Interval[Stk[tp]].st - 1;
        }
    }
     
    free(Tree);
    free(change);
    free(Stk);
    free(Interval);
    free(Sum);
    return ret;
}

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