Submission #863129

#	Time	Username	Problem	Language	Result	Execution time	Memory
863129		Pyqe	Overtaking (IOI23_overtaking)	C++17	100 / 100	1492 ms	132468 KiB

overtaking

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

using namespace std;

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

long long ln,n,m,d,nn=0,wg[1069],sl[1069],a[1069],tga[1069][1069],mxa[1069][1069],inf=2e18;
pair<long long,long long> as[1069][1069];
multiset<pair<long long,long long>> ms;

void init(int oln,int on,vector<long long> owg,vector<int> osl,int od,int om,vector<int> oa)
{
	long long i,j,r,k,l,w,p,mx;
	multiset<pair<long long,long long>>::iterator it;
	
	ln=oln;
	n=on;
	d=od;
	m=om;
	for(i=0;i<n;i++)
	{
		if(osl[i]>d)
		{
			nn++;
			wg[nn]=owg[i];
			sl[nn]=osl[i]-d;
		}
	}
	for(i=1;i<=m;i++)
	{
		a[i]=oa[i-1];
	}
	for(i=1;i<=nn;i++)
	{
		as[1][i]={wg[i],i};
	}
	sort(as[1]+1,as[1]+nn+1);
	for(i=2;i<=m;i++)
	{
		mx=-inf;
		for(r=1,j=1;j<=nn;j++)
		{
			w=as[i-1][j].fr;
			p=as[i-1][j].sc;
			for(;r<=nn&&as[i-1][r].fr<w;r++)
			{
				mx=max(mx,tga[i-1][r]);
			}
			tga[i-1][j]=max(w+sl[p]*(a[i]-a[i-1]),mx);
			as[i][j]={tga[i-1][j],p};
		}
		sort(as[i]+1,as[i]+nn+1);
	}
	ms.insert({-inf,-1});
	ms.insert({inf,-1});
	for(i=m-1;i;i--)
	{
		mxa[i][0]=-inf;
		for(j=1;j<=nn;j++)
		{
			k=as[i][j].fr;
			mxa[i][j]=max(mxa[i][j-1],tga[i][j]);
			l=mxa[i][j];
			it=prev(ms.lower_bound({l,-inf}));
			w=it->sc;
			if(next(it)->fr>l)
			{
				ms.insert({l,w});
			}
			if(w==-1)
			{
				w=l;
			}
			for(it=ms.lower_bound({k,-inf});it->fr<l;)
			{
				it++;
				ms.erase(prev(it));
			}
			ms.insert({k,w});
		}
	}
}

long long arrival_time(long long x)
{
	long long w;
	multiset<pair<long long,long long>>::iterator it;
	
	it=prev(ms.lower_bound({x,-inf}));
	w=it->sc;
	if(w!=-1)
	{
		x=w;
	}
	return x+d*ln;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 35 / 35