제출 #984127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
984127		CSQ31	고대 책들 (IOI17_books)	C++17	100 / 100	169 ms	52820 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
typedef long long int ll;
typedef pair<int,int> pii;
const int MAXN = 1e6+1;
int mn[MAXN],mx[MAXN];
ll ans = 0;
int n = 0;
vector<int>p;
void extend(int &l,int &r){
	int l0 = min(mn[l],mn[r]);
	int r0 = max(mx[l],mx[r]);
	while(l0 < l || r < r0){
		while(l0 < l){
			l--;
			l0 = min(l0,mn[l]);
			r0 = max(r0,mx[l]);
		}
		while(r0 > r){
			r++;
			l0 = min(l0,mn[r]);
			r0 = max(r0,mx[r]);
		}
	}
}
void solve(int l,int r){
	extend(l,r);
	//cout<<l<<" "<<r<<'\n';
	int rcost = 0;
	int lcost = 0;

	int l0 = l,r0 = r;
	int L = l,R = r;
	r++;
	while(r < n){
		rcost += 2;
		extend(l,r);
		if(l < l0)break;
		r++;
	}
	L = l;
	R = r;
	l = l0,r = r0;

	l--;
	while(l >= 0){
		lcost+=2;
		extend(l,r);
		if(r > r0)break;
		l--;
	}
	L = min(L,l);
	R = max(R,r);
	//cout<<L<<" "<<R<<" "<<lcost<<" "<<rcost<<'\n';
	if(R == n){ //end of the line
	    ans += rcost;
		ans += lcost;
		return;
	}

	ans += min(lcost,rcost);
	solve(L,R);
}
ll minimum_walk(vector<int>P, int s) {
	p = P;
	n = sz(p);
	for(int i=0;i<n;i++)ans+=abs(i-p[i]);
	vector<bool>vis(n,0);
	for(int i=0;i<n;i++){
		if(vis[i])continue;
		int cur = i;
		mn[i] = mx[i] = i;
		vector<int>path;
		while(!vis[cur]){
			vis[cur] = 1;
			path.push_back(cur);
			cur = p[cur];
		}
		for(int x:path){
			mn[i] = min(mn[i],x);
			mx[i] = max(mx[i],x);
		}
		for(int x:path){
			mn[x] = mn[i];
			mx[x] = mx[i];
		}
	}
	// for(int i=0;i<n;i++)cout<<mn[i]<<" ";
	// cout<<'\n';
	// for(int i=0;i<n;i++)cout<<mx[i]<<" ";
	// cout<<'\n';
	solve(s,s);
	for(int i=0;i<s;i++){
		if(i==p[i])ans-=2;
		else break;
	}
	for(int i=n-1;i>s;i--){
		if(i==p[i])ans-=2;
		else break;
	}
	return ans;	
}

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