oj.uz

Submission #13472

# Submission time Handle Problem Language Result Execution time Memory
13472 2015-02-21T04:51:08 Z baneling100 Holiday (IOI14_holiday) C++
100 / 100
 660 ms 19708 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19704 KB Output is correct
2 Correct 0 ms 19704 KB Output is correct
3 Correct 0 ms 19700 KB Output is correct
4 Correct 0 ms 19704 KB Output is correct
5 Correct 0 ms 19700 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 19704 KB Output is correct
2 Correct 357 ms 19708 KB Output is correct
3 Correct 465 ms 19704 KB Output is correct
4 Correct 406 ms 19704 KB Output is correct
5 Correct 526 ms 19704 KB Output is correct
6 Correct 194 ms 19700 KB Output is correct
7 Correct 285 ms 19708 KB Output is correct
8 Correct 311 ms 19704 KB Output is correct
9 Correct 158 ms 19708 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 19708 KB Output is correct
2 Correct 660 ms 19700 KB Output is correct
3 Correct 72 ms 19700 KB Output is correct
4 Correct 6 ms 19700 KB Output is correct
5 Correct 2 ms 19700 KB Output is correct
6 Correct 0 ms 19704 KB Output is correct
7 Correct 0 ms 19700 KB Output is correct
8 Correct 424 ms 19704 KB Output is correct
9 Correct 431 ms 19704 KB Output is correct