#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;
}
Compilation message
tournament.cpp: In member function 'bool Intv::operator<(const Intv&) const':
tournament.cpp:17:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
tournament.cpp: In function 'int FindPos(int)':
tournament.cpp:27:4: error: 'st' was not declared in this scope
if(st != t.st) return st < t.st;
^
tournament.cpp:27:10: error: 't' was not declared in this scope
if(st != t.st) return st < t.st;
^
tournament.cpp:29:8: error: 'en' was not declared in this scope
return en > t.en;
^
tournament.cpp:29:13: error: 't' was not declared in this scope
return en > t.en;
^
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:107:1: error: expected '}' at end of input
}
^
tournament.cpp:107:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
