Submission #14795

#	Time	Username	Problem	Language	Result	Execution time	Memory
14795		ainta	휴가 (IOI14_holiday)	C++98	30 / 100	154 ms	6636 KiB

holiday

#include"holiday.h"
#include<stdio.h>
#include<algorithm>
#define SZ 131082
using namespace std;

struct A{
    int a, num;
    bool operator<(const A &p)const{
        return a<p.a;
    }
}w[101000];

int P, D, Num[101000];
long long Res;

struct IdxTree{
    long long S;
    int C;
}IT[SZ+SZ];

void UDT(int a){
    while(a!=1){
        a>>=1;
        IT[a].S=IT[a+a].S+IT[a+a+1].S;
        IT[a].C=IT[a+a].C+IT[a+a+1].C;
    }
}
void On(int a){
    a=Num[a];
    IT[SZ+a].S=w[a].a,IT[SZ+a].C=1;
    UDT(SZ+a);
}
void Off(int a){
    a=Num[a];
    IT[SZ+a].S=0,IT[SZ+a].C=0;
    UDT(SZ+a);
}
long long Gap(int t){
    long long S=0;
    int nd = 1;
    while(nd<SZ){
        nd=nd+nd+1;
        if(IT[nd].C<=t){
            t-=IT[nd].C;
            S+=IT[nd].S;
            nd--;
        }
    }
    return S;
}

void Do1(int b, int e, int s, int l){
    if(b>e)return;
    int m = (b+e)>>1, i, x;
    long long M=0,S;
    for(i=m;i<=e;i++)On(i);
    for(i=s;i<=l;i++){
        On(i);
        S = Gap(D-(P-m)-(i-m));
        if(M<S)M=S,x=i;
    }
    Res=max(Res,M);
    if(b!=e){
        for(i=s;i<=l;i++)Off(i);
        Do1(b,m-1,s,x);
        for(i=m;i<=e;i++)Off(i);
        for(i=s;i<x;i++)On(i);
        Do1(m+1,e,x,l);
        for(i=s;i<x;i++)Off(i);
    }
    else{
        for(i=s;i<=l;i++)Off(i);
        for(i=m;i<=e;i++)Off(i);
    }
}

void Do2(int b, int e, int s, int l){
    if(b>e)return;
    int m = (b+e)>>1, i, x;
    long long M=0,S;
    for(i=b;i<=m;i++)On(i);
    for(i=l;i>=s;i--){
        On(i);
        S = Gap(D-(m-P)-(m-i));
        if(M<S)M=S,x=i;
    }
    Res=max(Res,M);
    if(b!=e){
        for(i=s;i<=l;i++)Off(i);
        Do2(m+1,e,x,l);
        for(i=b;i<=m;i++)Off(i);
        for(i=x+1;i<l;i++)On(i);
        Do2(b,m-1,s,x);
        for(i=x+1;i<l;i++)Off(i);
    }
    else{
        for(i=s;i<=l;i++)Off(i);
        for(i=b;i<=m;i++)Off(i);
    }
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    int i;
    D = d;
    for(i=0;i<n;i++){
        w[i].a = attraction[i];
        w[i].num = i;
    }
    sort(w,w+n);
    for(i=0;i<n;i++)Num[w[i].num]=i;
    P=start;
    Res=0;
    Do1(max(start-d/2,0),start,start,n-1);
    if(start)Do2(start,min(n-1,start+d/2),0,start-1);
    return Res;
}

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