oj.uz

Submission #16729

# Submission time Handle Problem Language Result Execution time Memory
16729 2015-09-12T01:25:27 Z CodingBug Jousting tournament (IOI12_tournament) C++
100 / 100
 110 ms 10896 KB 
#include <stdio.h>
#include <algorithm>
#define M 100000

using namespace std;

struct IdxTree{
    int a[1<<18],l,n;
    void init(int N){
        n=N;
        for(l=1;l<n;l<<=1) ;
        for(int i=0;i<n;i++) update(i,1);
    }
    void update(int x,int d){
        for(int i=x+l;i;i>>=1) a[i]+=d;
    }
    int getNum(int x){
        int i;
        for(i=1;i<l;){
            i*=2;
            if(a[i]<=x){
                x-=a[i];
                i++;
            }
        }
        if(i-l>=n) return n;
        return i-l;
    }
} itr;

struct Node{
    int val;
    Node *chi[2];
} *r;

int nxt[M+1],su[M+1];

int getNext(int x){
    if(x>=itr.n) return x;
    return itr.a[itr.l+x] ? x : nxt[x]=getNext(nxt[x]);
}

int setTree(int s,int e,Node *no,int *K){
    if(s==e) return no->val=K[s];
    int m=(s+e)/2;
    if(!no->chi[0]) no->chi[0]=new Node();
    if(!no->chi[1]) no->chi[1]=new Node();
    return no->val=max(setTree(s,m,no->chi[0],K),setTree(m+1,e,no->chi[1],K));
}

int getTree(int s,int e,int ss,int ee,Node *no){
    if(ss<=s && e<=ee) return no->val;
    if(e<ss || ee<s) return -1;
    int m=(s+e)/2;
    return max(getTree(s,m,ss,ee,no->chi[0]),getTree(m+1,e,ss,ee,no->chi[1]));
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    int i,v;
    itr.init(N);
    r=new Node();
    setTree(0,N-2,r,K);
    for(i=0;i<N;i++){
        nxt[i]=i+1;
    }

    for(i=0;i<C;i++){
        int s=itr.getNum(S[i]),e=itr.getNum(E[i]+1)-1;
        S[i]=s; E[i]=e;
        if(getTree(0,N-2,s,e-1,r)<R){
            su[s]++;
            su[e+1]--;
        }
        for(s=getNext(nxt[s]);s<=e;s=getNext(s)) itr.update(s,-1);
    }
    for(i=1;i<N;i++) su[i]+=su[i-1];
    for(v=0,i=1;i<N;i++) if(su[v]<su[i]) v=i;

    return v;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

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

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6496 KB Output is correct
2 Correct 105 ms 10364 KB Output is correct
3 Correct 30 ms 10896 KB Output is correct
4 Correct 80 ms 10364 KB Output is correct
5 Correct 93 ms 10064 KB Output is correct
6 Correct 93 ms 10100 KB Output is correct
7 Correct 103 ms 10364 KB Output is correct
8 Correct 110 ms 10364 KB Output is correct
9 Correct 31 ms 10804 KB Output is correct
10 Correct 37 ms 9612 KB Output is correct