Submission #13472

#	Time	Username	Problem	Language	Result	Execution time	Memory
13472		baneling100	Holiday (IOI14_holiday)	C++98	100 / 100	660 ms	19708 KiB

holiday

#include "holiday.h"
#include <algorithm>
#define N_MAX 200000
#define D_MAX 500000
#define M_MAX 262144

using namespace std;

struct attract {
    int value;
    int num;
    bool operator < (attract X) const {return value>X.value;}
} Attraction[N_MAX];
struct index {
    long long sum;
    int cnt;
} Idx[M_MAX<<1];
int N, Start, D, Location[N_MAX];
int M, restDay, isIdx;
long long goRight[D_MAX], goLeft[D_MAX], valueSum, Ans;

void insertIdx(int loc, int cost) {

    while(loc) {
        Idx[loc].sum+=cost;
        Idx[loc].cnt++;
        loc>>=1;
    }
}

void eraseIdx(int loc, int cost) {

    while(loc) {
        Idx[loc].sum-=cost;
        Idx[loc].cnt--;
        loc>>=1;
    }
}

void findIdx(int loc) {

    if(Idx[loc].cnt<=restDay) restDay-=Idx[loc].cnt, valueSum+=Idx[loc].sum;
    else {
        findIdx(loc<<1);
        if(restDay) findIdx((loc<<1)+1);
    }
}

void rightDC(int leftDay, int rightDay, int leftCity, int rightCity) {

    int i, midDay=(leftDay+rightDay)>>1, midCity=leftCity;

    if(leftDay>rightDay || leftCity>rightCity) return;
    for(i=leftCity ; i<=rightCity ; i++) {
        restDay=midDay-((i-Start)<<1), valueSum=0;
        if(restDay<0) break;
        isIdx=i, insertIdx(M+Location[i],Attraction[Location[i]].value);
        findIdx(1);
        if(goRight[midDay]<valueSum) goRight[midDay]=valueSum, midCity=i;
    }
    if(leftDay<=midDay-1) {
        while(isIdx>=leftCity) {
            eraseIdx(M+Location[isIdx],Attraction[Location[isIdx]].value);
            isIdx--;
        }
        rightDC(leftDay,midDay-1,leftCity,midCity);
    }
    if(midDay+1<=rightDay) {
        while(isIdx>=midCity) {
            eraseIdx(M+Location[isIdx],Attraction[Location[isIdx]].value);
            isIdx--;
        }
        rightDC(midDay+1,rightDay,midCity,rightCity);
    }
}

void leftDC(int leftDay, int rightDay, int leftCity, int rightCity) {

    int i, midDay=(leftDay+rightDay)>>1, midCity=rightCity;

    if(leftDay>rightDay || leftCity>rightCity) return;
    for(i=rightCity ; i>=leftCity ; i--) {
        restDay=midDay-(Start-1-i), valueSum=0;
        if(restDay<0) break;
        isIdx=i, insertIdx(M+Location[i],Attraction[Location[i]].value);
        findIdx(1);
        if(goLeft[midDay]<valueSum) goLeft[midDay]=valueSum, midCity=i;
    }
    if(leftDay<=midDay-1) {
        while(isIdx<=rightCity) {
            eraseIdx(M+Location[isIdx],Attraction[Location[isIdx]].value);
            isIdx++;
        }
        leftDC(leftDay,midDay-1,midCity,rightCity);
    }
    if(midDay+1<=rightDay) {
        while(isIdx<=midCity) {
            eraseIdx(M+Location[isIdx],Attraction[Location[isIdx]].value);
            isIdx++;
        }
        leftDC(midDay+1,rightDay,leftCity,midCity);
    }
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {

    int i;

    N=n, Start=start, D=d;
    for(M=1 ; M<N ; M<<=1);
    for(i=0 ; i<N ; i++) Attraction[i].value=attraction[i], Attraction[i].num=i;
    sort(Attraction,Attraction+N);
    for(i=0 ; i<N ; i++) Location[Attraction[i].num]=i;
    isIdx=Start-1;
    rightDC(0,D-1,Start,N-1);
    while(isIdx>=Start) {
        eraseIdx(M+Location[isIdx],Attraction[Location[isIdx]].value);
        isIdx--;
    }
    isIdx=Start;
    leftDC(0,D-1,0,Start-1);
    while(isIdx<=Start-1) {
        eraseIdx(M+Location[isIdx],Attraction[Location[isIdx]].value);
        isIdx++;
    }
    for(i=0 ; i<D ; i++) {
        Ans=max(Ans,goRight[i]+goLeft[D-i-1]);
        goRight[i]=goLeft[D-i-1]=0;
    }
    for(i=0 ; i<N ; i++) {
        Attraction[i].num=N-1-Attraction[i].num;
        Location[Attraction[i].num]=i;
    }
    Start=N-1-Start;
    isIdx=Start-1;
    rightDC(0,D-1,Start,N-1);
    while(isIdx>=Start) {
        eraseIdx(M+Location[isIdx],Attraction[Location[isIdx]].value);
        isIdx--;
    }
    isIdx=Start;
    leftDC(0,D-1,0,Start-1);
    for(i=0 ; i<D ; i++)
        Ans=max(Ans,goRight[i]+goLeft[D-i-1]);
    return Ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53