Submission #8085

#	Time	Username	Problem	Language	Result	Execution time	Memory
8085		gs13068	Holiday (IOI14_holiday)	C++98	100 / 100	404 ms	26364 KiB

holiday

#include"holiday.h"
#include<algorithm>

std::pair<int,int> b[100000];
int c[100000];
long long l[250001];
int lc[250001];
long long r[250001];
int rc[250001];

struct rec
{
	int s;
	int e;
	int l;
	int r;
} q[1000000];
int qn;

long long sum[200001];
int cnt[200001];

long long findMaxAttraction(int n,int m,int d,int a[])
{
	long long te;
	int i,j,k,p,t,tt,cut;
	for(i=0;i<n;i++)
	{
		b[i].first=a[i];
		b[i].second=i;
	}
    std::sort(b,b+n);
    for(i=0;i<n;i++)c[b[i].second]=n-i;

	for(i=1;i<=200000;i++)sum[i]=cnt[i]=0;
	lc[0]=m;
	qn=0;
    q[qn].s=1;
    q[qn].e=d;
    q[qn].l=m;
    q[qn].r=n-1;
    qn++;
    j=m;
    for(i=0;i<qn;i++)if(q[i].s<=q[i].e)
	{
		p=(q[i].s+q[i].e)/2;
		while(j<q[i].l)
		{
			j++;
			k=c[j];
            while(k<=200000)
			{
				sum[k]+=a[j];
                cnt[k]++;
                k+=k&-k;
			}
		}
		while(j>q[i].l)
		{
			k=c[j];
            while(k<=200000)
			{
				sum[k]-=a[j];
                cnt[k]--;
                k+=k&-k;
			}
			j--;
		}
		k=0;
		tt=p+m-j;
		for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=tt)
		{
			tt-=cnt[k|(1<<t)];
			k|=1<<t;
		}
        while(k)
		{
			l[p]+=sum[k];
			k-=k&-k;
		}
		cut=j;
		while(j<q[i].r)
		{
			j++;
			k=c[j];
            while(k<=200000)
			{
				sum[k]+=a[j];
                cnt[k]++;
                k+=k&-k;
			}
			k=0;
			tt=p+m-j;
			for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=tt)
			{
				tt-=cnt[k|(1<<t)];
				k|=1<<t;
			}
			te=0;
			while(k)
			{
				te+=sum[k];
				k-=k&-k;
			}
			if(te>l[p])
			{
				l[p]=te;
				cut=j;
			}
		}
		lc[p]=cut;
		q[qn].s=q[i].s;
		q[qn].e=p-1;
		q[qn].l=q[i].l;
        q[qn].r=cut;
        qn++;
		q[qn].s=p+1;
		q[qn].e=q[i].e;
		q[qn].l=cut;
        q[qn].r=q[i].r;
        qn++;
	}

	for(i=1;i<=200000;i++)sum[i]=cnt[i]=0;
	rc[0]=m;
	qn=0;
    q[qn].s=1;
    q[qn].e=d;
    q[qn].l=0;
    q[qn].r=m;
    qn++;
    j=m;
    for(i=0;i<qn;i++)if(q[i].s<=q[i].e)
	{
		p=(q[i].s+q[i].e)/2;
		while(j>q[i].r)
		{
			j--;
			k=c[j];
            while(k<=200000)
			{
				sum[k]+=a[j];
                cnt[k]++;
                k+=k&-k;
			}
		}
		while(j<q[i].r)
		{
			k=c[j];
            while(k<=200000)
			{
				sum[k]-=a[j];
                cnt[k]--;
                k+=k&-k;
			}
			j++;
		}
		k=0;
		tt=p+j-m;
		for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=tt)
		{
			tt-=cnt[k|(1<<t)];
			k|=1<<t;
		}
        while(k)
		{
			r[p]+=sum[k];
			k-=k&-k;
		}
		cut=j;
		while(j>q[i].l)
		{
			j--;
			k=c[j];
            while(k<=200000)
			{
				sum[k]+=a[j];
                cnt[k]++;
                k+=k&-k;
			}
			k=0;
			tt=p+j-m;
			for(t=16;t>=0;t--)if(cnt[k|(1<<t)]<=tt)
			{
				tt-=cnt[k|(1<<t)];
				k|=1<<t;
			}
			te=0;
			while(k)
			{
				te+=sum[k];
				k-=k&-k;
			}
			if(te>r[p])
			{
				r[p]=te;
				cut=j;
			}
		}
		rc[p]=cut;
		q[qn].s=q[i].s;
		q[qn].e=p-1;
		q[qn].l=cut;
        q[qn].r=q[i].r;
        qn++;
		q[qn].s=p+1;
		q[qn].e=q[i].e;
		q[qn].l=q[i].l;
        q[qn].r=cut;
        qn++;
	}
	te=0;
	for(i=0;i<=d;i++)
	{
        if(d-i-lc[i]+m>=0)te=std::max(te,r[d-i-lc[i]+m]+l[i]);
        if(d-i-lc[i]+m-1>=0)te=std::max(te,r[d-i-lc[i]+m-1]+l[i]+a[m]);
        if(d-i+rc[i]-m>=0)te=std::max(te,l[d-i+rc[i]-m]+r[i]);
        if(d-i+rc[i]-m-1>=0)te=std::max(te,l[d-i+rc[i]-m-1]+r[i]+a[m]);
	}
	return te;
}

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