oj.uz

Submission #8085

# Submission time Handle Problem Language Result Execution time Memory
8085 2014-08-28T13:11:46 Z gs13068 Holiday (IOI14_holiday) C++
100 / 100
 404 ms 26364 KB 
#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.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 26356 KB Output is correct
2 Correct 296 ms 26356 KB Output is correct
3 Correct 308 ms 26364 KB Output is correct
4 Correct 304 ms 26360 KB Output is correct
5 Correct 380 ms 26360 KB Output is correct
6 Correct 120 ms 26356 KB Output is correct
7 Correct 200 ms 26360 KB Output is correct
8 Correct 232 ms 26356 KB Output is correct
9 Correct 112 ms 26356 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26360 KB Output is correct
2 Correct 12 ms 26360 KB Output is correct
3 Correct 8 ms 26360 KB Output is correct
4 Correct 4 ms 26356 KB Output is correct
5 Correct 8 ms 26364 KB Output is correct
6 Correct 4 ms 26356 KB Output is correct
7 Correct 4 ms 26360 KB Output is correct
8 Correct 0 ms 26360 KB Output is correct
9 Correct 0 ms 26356 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 26364 KB Output is correct
2 Correct 356 ms 26360 KB Output is correct
3 Correct 128 ms 26364 KB Output is correct
4 Correct 4 ms 26360 KB Output is correct
5 Correct 0 ms 26360 KB Output is correct
6 Correct 0 ms 26360 KB Output is correct
7 Correct 4 ms 26364 KB Output is correct
8 Correct 404 ms 26360 KB Output is correct
9 Correct 400 ms 26360 KB Output is correct