oj.uz

Submission #38878

# Submission time Handle Problem Language Result Execution time Memory
38878 2018-01-07T13:52:07 Z andy627 Jousting tournament (IOI12_tournament) C++14
100 / 100
 126 ms 8160 KB 
#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.0 / 17.0

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

Subtask #2
32.0 / 32.0

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

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7464 KB Output is correct
2 Correct 96 ms 8160 KB Output is correct
3 Correct 26 ms 7408 KB Output is correct
4 Correct 126 ms 8160 KB Output is correct
5 Correct 119 ms 8124 KB Output is correct
6 Correct 89 ms 7896 KB Output is correct
7 Correct 116 ms 8160 KB Output is correct
8 Correct 99 ms 8160 KB Output is correct
9 Correct 19 ms 7408 KB Output is correct
10 Correct 26 ms 7408 KB Output is correct