oj.uz

Submission #7768

# Submission time Handle Problem Language Result Execution time Memory
7768 2014-08-18T16:20:41 Z baneling100 Jousting tournament (IOI12_tournament) C++
100 / 100
 136 ms 31580 KB 
#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.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21216 KB Output is correct
2 Correct 4 ms 21852 KB Output is correct
3 Correct 0 ms 21620 KB Output is correct
4 Correct 4 ms 21852 KB Output is correct
5 Correct 0 ms 21848 KB Output is correct
6 Correct 4 ms 21548 KB Output is correct
7 Correct 0 ms 21852 KB Output is correct
8 Correct 4 ms 21852 KB Output is correct
9 Correct 0 ms 21620 KB Output is correct
10 Correct 0 ms 21856 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 26272 KB Output is correct
2 Correct 132 ms 31580 KB Output is correct
3 Correct 60 ms 26268 KB Output is correct
4 Correct 136 ms 31580 KB Output is correct
5 Correct 128 ms 31544 KB Output is correct
6 Correct 88 ms 31316 KB Output is correct
7 Correct 132 ms 31580 KB Output is correct
8 Correct 136 ms 31580 KB Output is correct
9 Correct 44 ms 26220 KB Output is correct
10 Correct 48 ms 26256 KB Output is correct