Submission #986365

#	Time	Username	Problem	Language	Result	Execution time	Memory
986365		Pyqe	Holiday (IOI14_holiday)	C++17	100 / 100	1630 ms	8020 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long nn=0,p[2],sm,dd,inf=1e18;
queue<pair<pair<long long,long long>,pair<long long,long long>>> q;
multiset<long long> ms[2];
multiset<long long>::iterator it;

void blc()
{
	for(;nn<dd&&!ms[1].empty();nn++)
	{
		it=ms[1].end();
		it--;
		ms[0].insert(*it);
		sm+=*it;
		ms[1].erase(it);
	}
	for(;nn>dd&&!ms[0].empty();nn--)
	{
		it=ms[0].begin();
		ms[1].insert(*it);
		sm-=*it;
		ms[0].erase(it);
	}
}

long long findMaxAttraction(int n, int st, int d, int a[])
{
	long long i,ii,iii,lh,rh,md,lb,rb,w,mx,e,z=-inf;
	pair<long long,long long> mxe;
	
	for(ii=0;ii<2;ii++)
	{
		p[0]=inf;
		q.push({{max(st-d,0),st},{max(st-d,0),n-1}});
		for(;!q.empty();)
		{
			lh=q.front().fr.fr;
			rh=q.front().fr.sc;
			lb=q.front().sc.fr;
			rb=q.front().sc.sc;
			q.pop();
			if(lh>rh)
			{
				continue;
			}
			md=(lh+rh)/2;
			if(md<p[0])
			{
				for(iii=0;iii<2;iii++)
				{
					p[iii]=-iii;
					ms[iii].clear();
				}
				nn=0;
				sm=0;
				dd=d-st+1;
			}
			mxe={-inf,-1};
			for(i=max(lb,md);i<=rb;i++)
			{
				for(;p[1]<i;)
				{
					p[1]++;
					ms[0].insert(a[p[1]]);
					nn++;
					sm+=a[p[1]];
					dd--;
					blc();
				}
				for(;p[0]<md;p[0]++)
				{
					it=ms[0].find(a[p[0]]);
					if(it!=ms[0].end())
					{
						ms[0].erase(it);
						nn--;
						sm-=a[p[0]];
					}
					else
					{
						ms[1].erase(ms[1].find(a[p[0]]));
					}
					dd+=2;
					blc();
				}
				w=sm;
				if(dd<0)
				{
					w=-inf;
				}
				mxe=max(mxe,{w,i});
			}
			mx=mxe.fr;
			e=mxe.sc;
			z=max(z,mx);
			q.push({{lh,md-1},{lb,e}});
			q.push({{md+1,rh},{e,rb}});
		}
		st=n-1-st;
		for(i=0;i<=n/2;i++)
		{
			swap(a[i],a[n-1-i]);
		}
	}
	return z;
}

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