Submission #16729

#	Time	Username	Problem	Language	Result	Execution time	Memory
16729		CodingBug	Jousting tournament (IOI12_tournament)	C++98	100 / 100	110 ms	10896 KiB

tournament

#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 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51