Submission #901501

#	Time	Username	Problem	Language	Result	Execution time	Memory
901501		nxteru	Ancient Books (IOI17_books)	C++14	100 / 100	102 ms	23804 KiB

books

#include <bits/stdc++.h>
using namespace std;
using ll =long long;
template<class t,class u>bool chmax(t&a,u b){if(a<b)a=b;return a<b;}
template<class t,class u>bool chmin(t&a,u b){if(b<a)a=b;return b<a;}
#define N 1000005
int l[N],r[N];
bool vis[N];

void extend(int &nl,int &nr,int tl=-1,int tr=-1){
	if(tl==-1)tl=nl+1;
	if(tr==-1)tr=nl;
	while(nl<tl||tr<nr){
		if(nl<tl){
			tl--;
			chmin(nl,l[tl]);
			chmax(nr,r[tl]);
		}
		if(tr<nr){
			tr++;
			chmin(nl,l[tr]);
			chmax(nr,r[tr]);
		}
	}
}
ll minimum_walk(vector<int>p, int s){
	int n=p.size();
	for(int i=0;i<n;i++){
		int v=i;
		while(!vis[v]){
			vis[v]=true;
			l[v]=i;
			v=p[v];
		}
	}
	for(int i=0;i<n;i++)vis[i]=false;
	for(int i=n-1;i>=0;i--){
		int v=i;
		while(!vis[v]){
			vis[v]=true;
			r[v]=i;
			v=p[v];
		}
	}
	int gl=0,gr=n-1;
	while(gl<n&&p[gl]==gl)gl++;
	while(gr>=0&&p[gr]==gr)gr--;
	if(gl>gr)return 0;
	ll ans=0;
	for(int i=0;i<n;i++)ans+=abs(p[i]-i);
	int nl=s,nr=s;
	extend(nl,nr);
	while(gl<nl||nr<gr){
		ll tmpl=0;
		int l_nxtl=nl,l_nxtr=nr;
		while(gl<l_nxtl&&l_nxtr<=nr){
			tmpl+=2;
			l_nxtl--;
			extend(l_nxtl,l_nxtr,l_nxtl+1,l_nxtr);
		}
		ll tmpr=0;
		int r_nxtl=nl,r_nxtr=nr;
		while(gr>r_nxtr&&r_nxtl>=nl){
			tmpr+=2;
			r_nxtr++;
			extend(r_nxtl,r_nxtr,r_nxtl,r_nxtr-1);
		}
		if(l_nxtl==r_nxtl&&l_nxtr==r_nxtr){
			ans+=min(tmpl,tmpr);
			nl=l_nxtl;
			nr=l_nxtr;
		}else{
			ans+=tmpl;
			ans+=tmpr;
			nl=min(l_nxtl,r_nxtl);
			nr=max(l_nxtr,r_nxtr);
		}
	}
	return ans;
}

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