Submission #7768

#	Time	Username	Problem	Language	Result	Execution time	Memory
7768		baneling100	Jousting tournament (IOI12_tournament)	C++98	100 / 100	136 ms	31580 KiB

tournament

#include <stdio.h>
#include <algorithm>
#include <vector>
#define INF 0x7fffffff

using namespace std;

typedef pair <int,int> ppair;
typedef pair <int,ppair> pppair;
static vector <pppair> A;
static int M, Idx[2621044], Left[1000000], Stack[500000][3], Top, Ans=-1, AnsLoc, Lb, Rb, Value;

int FindLoc(int Num) {

    int Loc=1;

    while(Loc<M) {
        Loc*=2;
        if(Num>Idx[Loc]) {
            Num-=Idx[Loc];
            Loc++;
        }
    }
    return Loc;
}

void ReNew(int X, int Y) {

    int i, Loc=Left[Y-M], Temp;

    Left[Y-M]=Left[X-M];
    while(1) {
        Temp=Loc;
        while(Temp) {
            Idx[Temp]--;
            Temp/=2;
        }
        Temp=Left[Loc-M];
        Left[Loc-M]=0;
        if(Loc==X)
            break;
        Loc=Temp;
    }
}

void IdxTree(int LL, int RR, int Now) {

    int Mid=(LL+RR)/2;

    if(Lb<=LL && RR<=Rb)
        Value&=Idx[Now];
    else {
        if(Lb<=Mid)
            IdxTree(LL,Mid,2*Now);
        if(Mid+1<=Rb)
            IdxTree(Mid+1,RR,2*Now+1);
    }
}

int OK(int LeftBound, int RightBound) {

    Lb=LeftBound;
    Rb=RightBound;
    Value=1;
    if(Lb<=Rb)
        IdxTree(0,M-1,1);
    return Value;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

    int i, X, Y, Size;

    for(M=1 ; M<N ; M*=2);
    for(i=M ; i<2*M ; i++) {
        Idx[i]=1;
        Left[i-M]=i-1;
    }
    for(i=M-1 ; i>=1 ; i--)
        Idx[i]=Idx[2*i]+Idx[2*i+1];
    for(i=0 ; i<C ; i++) {
        X=FindLoc(S[i]+1);
        Y=FindLoc(E[i]+1);
        S[i]=Left[X-M]+1-M;
        E[i]=Y-M;
        ReNew(X,Y);
    }
    for(i=M ; i<M+N ; i++) {
        if(K[i-M]<R)
            Idx[i]=1;
        else
            Idx[i]=0;
    }
    for(i=M-1 ; i>=1 ; i--)
        Idx[i]=Idx[2*i]&Idx[2*i+1];
    for(i=0 ; i<C ; i++) {
        A.push_back(make_pair(S[i],make_pair(-E[i],-1)));
        A.push_back(make_pair(E[i],make_pair(-S[i],1)));
    }
    for(i=0 ; i<N ; i++) {
        A.push_back(make_pair(i,make_pair(-i,-1)));
        A.push_back(make_pair(i,make_pair(-i,1)));
    }
    sort(A.begin(),A.end());
    Size=A.size();
    for(i=0 ; i<Size ; i++) {
        if(A[i].second.second==-1) {
            Top++;
            Stack[Top][0]=A[i].first;
            Stack[Top][1]=-INF;
        }
        else {
            if(Stack[Top][0]==A[i].first) {
                Stack[Top][1]=0;
                Stack[Top][2]=A[i].first;
            }
            if(OK(Stack[Top][0],A[i].first-1)) {
                if(Ans<Stack[Top][1]) {
                    Ans=Stack[Top][1];
                    AnsLoc=Stack[Top][2];
                }
                if(Stack[Top-1][1]<Stack[Top][1]+1) {
                    Stack[Top-1][1]=Stack[Top][1]+1;
                    Stack[Top-1][2]=Stack[Top][2];
                }
            }
            Top--;
        }
    }
    return AnsLoc;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51