Submission #986397

#	Time	Username	Problem	Language	Result	Execution time	Memory
986397		Pyqe	Ancient Books (IOI17_books)	C++17	100 / 100	269 ms	82364 KiB

books

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

using namespace std;

const long long inf=1e18;
long long n,a[1000069],fh[2][1000069],nr[1000069],dsu[1000069];
bitset<1000069> vtd,vtd2;
queue<long long> q;

long long fd(long long x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}

void ad(long long x,long long w)
{
	long long i,p,sz;
	vector<long long> v;
	
	for(p=fh[0][x];fd(p)<=fh[1][x];dsu[fd(p)]=fd(fd(p)+1))
	{
		q.push(fd(p));
		nr[fd(p)]=w;
		v.push_back(fd(p));
	}
	sz=v.size();
	for(i=0;i<sz;i++)
	{
		ad(v[i],w);
	}
}

long long minimum_walk(vector<int> aa,int st)
{
	long long i,ii,u,k,p,mn,mx,z=0;
	
	st++;
	n=aa.size();
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1]+1;
		z+=abs(i-a[i]);
		nr[i]=inf;
	}
	for(i=1;i<=n;i++)
	{
		if(!vtd[i])
		{
			mn=i;
			mx=i;
			for(p=i;!vtd[p];p=a[p])
			{
				vtd[p]=1;
				mn=min(mn,p);
				mx=max(mx,p);
			}
			for(p=i;!vtd2[p];p=a[p])
			{
				vtd2[p]=1;
				fh[0][p]=mn;
				fh[1][p]=mx;
			}
		}
	}
	for(i=1;i<=n+1;i++)
	{
		dsu[i]=i;
	}
	ad(st,0);
	mx=0;
	for(;!q.empty();)
	{
		k=q.front();
		q.pop();
		if(fh[0][k]<=st&&fh[1][k]>=st)
		{
			mx=nr[k];
		}
		for(ii=0;ii<2;ii++)
		{
			u=!ii*2-1;
			if(k+u&&k+u<=n)
			{
				ad(k+u,nr[k]+1);
			}
		}
	}
	z+=mx*2;
	mn=st;
	mx=st;
	for(i=1;i<=n;i++)
	{
		if(a[i]!=i)
		{
			mn=min(mn,i);
			mx=max(mx,i);
		}
	}
	k=0;
	for(i=mn;i<mx;i++)
	{
		k=max(k,fh[1][i]);
		z+=2*(k==i);
	}
	return z;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30