Submission #903291

#	Time	Username	Problem	Language	Result	Execution time	Memory
903291		Faisal_Saqib	Holiday (IOI14_holiday)	C++17	47 / 100	453 ms	3916 KiB

holiday

#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
const int N=1e6+200;
int MN=3003;
int seg_cnt[N];
long long seg_sum[N];
void Update(int i,ll val=-1,int v=1,int s=0,int e=MN)
{
	if(i<s or e<i)
		return;
	if(s==e)
	{
		seg_cnt[v]++;
		if(val==-1)
			seg_sum[v]+=i;
		else
		{
			seg_sum[v]+=val;
		}
		return;
	}
	int mid=(s+e)/2;
	Update(i,val,2*v,s,mid);
	Update(i,val,2*v+1,1+mid,e);
	seg_cnt[v]=seg_cnt[2*v]+seg_cnt[2*v+1];
	seg_sum[v]=seg_sum[2*v]+seg_sum[2*v+1];
}
void Update1(int i,ll val=-1,int v=1,int s=0,int e=MN)
{
	if(i<s or e<i)
		return;
	if(s==e)
	{
		seg_cnt[v]--;
		if(val==-1)
			seg_sum[v]-=i;
		else
			seg_sum[v]-=val;
		return;
	}
	int mid=(s+e)/2;
	Update1(i,val,2*v,s,mid);
	Update1(i,val,2*v+1,1+mid,e);
	seg_cnt[v]=seg_cnt[2*v]+seg_cnt[2*v+1];
	seg_sum[v]=seg_sum[2*v]+seg_sum[2*v+1];
}
int get_cnt(int l,int r,int v=1,int s=0,int e=MN)
{
	if(r<s or e<l)
		return 0;
	if(l<=s and e<=r)
		return seg_cnt[v];
	int mid=(s+e)/2;
	return get_cnt(l,r,2*v,s,mid)+get_cnt(l,r,2*v+1,mid+1,e);
}
long long get_sum(int l,int r,int v=1,int s=0,int e=MN)
{
	if(r<s or e<l)
		return 0;
	if(l<=s and e<=r)
		return seg_sum[v];
	int mid=(s+e)/2;
	return get_sum(l,r,2*v,s,mid)+get_sum(l,r,2*v+1,mid+1,e);
}
int MGL;
int heavy(int tmp,int pre=0,int v=1,int s=0,int e=MN)
{
	if(s==e)
		return s;
	int mid=(s+e)/2;
	if((pre+seg_cnt[2*v+1]+tmp)>MGL)
	{
		return heavy(tmp,pre,2*v+1,mid+1,e);
	}
	else
	{
		return heavy(tmp,pre+seg_cnt[2*v+1],2*v,s,mid);
	}
}
long long findMaxAttraction(int n, int cc, int d, int a[])
{
	MGL=d;
	vector<int> op,dp;
	for(int i=0;i<n;i++)
		op.push_back(a[i]);
	sort(begin(op),end(op));
	op.resize(unique(begin(op),end(op))-begin(op));
	for(int i=0;i<n;i++)
		dp.push_back(lower_bound(begin(op),end(op),a[i])-begin(op));
	long long ans=0;
	for(int left=cc;left>=0;left--)
	{
		Update(dp[left],a[left]);
		{
			int right=cc;
			ll tmie=min(right-cc,cc-left)+right-left;
			if(tmie<=d)
			{
				long long cur;
				if((get_cnt(0,MN)+tmie)<=d)
				{
					cur=get_sum(0,MN);
				}
				else
				{
					int s=heavy(tmie);
					cur=get_sum(s+1,MN);
					if(s!=-1)
						cur+=(op[s]*(d-tmie-get_cnt(s+1,MN)));
				}
				ans=max(ans,cur);
			}
		}
		for(int right=cc+1;right<n;right++)
		{
			Update(dp[right],a[right]);
			ll tmie=min(right-cc,cc-left)+right-left;
			if(tmie>d)
				continue;
			long long cur;
			if((get_cnt(0,MN)+tmie)<=d)
			{
				cur=get_sum(0,MN);
			}
			else
			{
				int s=heavy(tmie);
				cur=get_sum(s+1,MN);
				if(s!=-1)
					cur+=(op[s]*(d-tmie-get_cnt(s+1,MN)));
			}
			ans=max(ans,cur);
		}
		for(int right=cc+1;right<n;right++)
			Update1(dp[right],a[right]);
	}
	return ans;
}

Compilation message (stderr)

holiday.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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