oj.uz

Submission #845

# Submission time Handle Problem Language Result Execution time Memory
845 2013-03-30T00:25:41 Z tncks0121 Jousting tournament (IOI12_tournament) C++
100 / 100
 72 ms 6192 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Correct 0 ms 1088 KB Output is correct
4 Correct 0 ms 1088 KB Output is correct
5 Correct 0 ms 1088 KB Output is correct
6 Correct 0 ms 1088 KB Output is correct
7 Correct 0 ms 1088 KB Output is correct
8 Correct 0 ms 1088 KB Output is correct
9 Correct 0 ms 1088 KB Output is correct
10 Correct 0 ms 1088 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 4 ms 1348 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct
4 Correct 0 ms 1348 KB Output is correct
5 Correct 0 ms 1356 KB Output is correct
6 Correct 0 ms 1216 KB Output is correct
7 Correct 0 ms 1348 KB Output is correct
8 Correct 0 ms 1348 KB Output is correct
9 Correct 0 ms 1216 KB Output is correct
10 Correct 4 ms 1352 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3200 KB Output is correct
2 Correct 60 ms 6192 KB Output is correct
3 Correct 20 ms 4312 KB Output is correct
4 Correct 72 ms 6192 KB Output is correct
5 Correct 64 ms 6092 KB Output is correct
6 Correct 60 ms 5528 KB Output is correct
7 Correct 64 ms 6192 KB Output is correct
8 Correct 72 ms 6192 KB Output is correct
9 Correct 16 ms 4312 KB Output is correct
10 Correct 28 ms 4312 KB Output is correct