제출 #790559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790559		FEDIKUS	고대 책들 (IOI17_books)	C++17	50 / 100	2054 ms	31568 KiB

books

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

using ll = long long;
using namespace std;

const int maxn=1e6+10;

int n;
int mini[maxn];
int maxi[maxn];
bool bio[maxn];
int dsu[maxn],siz[maxn];

int cale(int a){return a==dsu[a] ? a:cale(dsu[a]);}
void join(int a,int b){
	a=cale(a); b=cale(b);
	if(a==b) return;
	if(siz[a]<siz[b]) swap(a,b);
	dsu[b]=a;
	siz[a]+=siz[b];
	maxi[a]=max(maxi[a],maxi[b]);
	mini[a]=min(mini[a],mini[b]);
}
void init(){
	for(int i=0;i<n;i++){dsu[i]=i; siz[i]=1; maxi[i]=i; mini[i]=i;}
}

ll minimum_walk(vector<int> p, int s) {
	n=p.size();
	init();
	ll ret=0;
	int imal=n,imar=-1;
	for(int i=0;i<n;i++){
		if(p[i]!=i) imal=min(imal,i);
		if(p[i]!=i) imar=i;
		ret+=abs(p[i]-i);
		if(bio[i]) continue;
		int tren=i;
		while(!bio[tren]){
			bio[tren]=true;
			join(tren,p[tren]);
			tren=p[tren];
		}
	}
	imal=min(imal,s);
	imar=max(imar,s);
	int l=s,r=s;
	int tl=mini[cale(s)],tr=maxi[cale(s)];
	int dodaol=0,dodaor=0;
	while(l!=imal || r!=imar){
		bool pl=false,pr=false;
		if(l>imal && maxi[cale(l-1)]<=r){
			pl=true;
			l--;
			if(l<tl){
				ret+=2;
				dodaol++;
			}
			tl=min(tl,mini[cale(l)]);
		}
		if(r<imar && mini[cale(r+1)]>=l){
			pr=true;
			r++;
			if(r>tr){
				ret+=2;
				dodaor++;
			}
			tr=max(tr,maxi[cale(r)]);
		}
		if(pl || pr) continue;
		ret-=2*max(dodaol,dodaor);
		ret+=2;
		dodaol=0;
		dodaor=0;
	}
	return ret;
}

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