Submission #15695

#	Time	Username	Problem	Language	Result	Execution time	Memory
15695		ainta	Holiday (IOI14_holiday)	C++98	100 / 100	1208 ms	6636 KiB

holiday

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

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

int Num[101000], D, st;

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

long long Res;

void Ins(int nd, int b, int e, int x, int ck){
    if(b == e){
        if(ck == 1)IT[nd].num = 1, IT[nd].S = w[x].a;
        else IT[nd].num = 0, IT[nd].S = 0;
        return;
    }
    int m = (b+e)>>1;
    if(x <= m)Ins(nd*2,b,m,x,ck);
    else Ins(nd*2+1,m+1,e,x,ck);
    IT[nd].S=IT[nd*2].S+IT[nd*2+1].S;
    IT[nd].num=IT[nd*2].num+IT[nd*2+1].num;
}

void On(int x){
    Ins(1, 0, SZ-1, x, 1);
}
void Off(int x){
    Ins(1, 0, SZ-1, x, 0);
}

long long Gap(int nd, int b, int e, int k){
    if(IT[nd].num <= k)return IT[nd].S;
    int m = (b+e)>>1;
    if(IT[nd*2+1].num >= k)return Gap(nd*2+1,m+1,e,k);
    return IT[nd*2+1].S + Gap(nd*2,b,m,k-IT[nd*2+1].num);
}

void Do(int st, int b, int e, int s, int l){
    if(b>e || s>l)return;
    int i, mid = (b+e)>>1, t;
    for(i=mid;i<=e;i++){
        On(Num[i]);
    }
    long long M = -1, tp;
    int pv = s;
    for(i=s;i<=l;i++){
        t = D -(st - mid) - (i - mid);
        if(t<0)break;
        On(Num[i]);
        tp = Gap(1, 1, SZ, t);
        if(M < tp){
            M = tp, pv = i;
        }
    }
    Res = max(Res, M);
    for(i=s+1;i<=l;i++)Off(Num[i]);
    Do(st,b,mid-1,s,pv);
    for(i=mid;i<=e;i++)Off(Num[i]);
    for(i=s;i<pv;i++)On(Num[i]);
    Do(st,mid+1,e,pv,l);
    for(i=s;i<pv;i++)Off(Num[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);
    st = start;
    for(i=0;i<n;i++)Num[w[i].num]=i;
    Do(start, 0, start, start, n-1);
    for(i=0;i<n;i++)Num[n-1-w[i].num]=i;
    Do(n-1-start, 0, n-1-start, n-1-start, n-1);
    return Res;
}

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