| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 20235 | rubabredwan | 마상시합 토너먼트 (IOI12_tournament) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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{
}
} *Interval;
int FindPos(int pos){
int nd = 1, width = TS;
while(nd < TS){
if(st != t.st) return st < t.st;
return en > t.en;
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;
}