Submission #391013

#	Time	Username	Problem	Language	Result	Execution time	Memory
391013		alishahali1382	Ancient Books (IOI17_books)	C++14	100 / 100	226 ms	30660 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
 
const int inf=1000000100;
const int MAXN=1000010;
 
ll ans; // :)
int n, m, k, s, L, R;
int P[MAXN], ps[MAXN];
int mn[MAXN], mx[MAXN];
 
pii fix(int l, int r){
	int ll=min({l, mn[l], mn[r]}), rr=max({r, mx[l], mx[r]});
	while (ll<l || r<rr){
		if (ll<l){
			l--;
			ll=min(ll, mn[l]);
			rr=max(rr, mx[l]);
		}
		if (r<rr){
			r++;
			ll=min(ll, mn[r]);
			rr=max(rr, mx[r]);
		}
	}
	return {l, r};
}
 
ll minimum_walk(vector<int> _p, int s){
	n=_p.size();
	for (int i=0; i<n; i++){
		P[i]=_p[i];
		ans+=abs(i-P[i]);
		ps[min(i, P[i])]++;
		ps[max(i, P[i])]--;
	}
	if (!ans) return 0;
	L=0;
	R=n-1;
	while (P[L]==L) L++;
	while (P[R]==R) R--;
	for (int i=1; i<=R; i++) ps[i]+=ps[i-1];
	if (s<=L || R<=s){
		for (int i=L; i+1<=R; i++) if (!ps[i]) ans+=2;
		if (s<L) ans+=2*(L-s);
		if (R<s) ans+=2*(s-R);
		return ans;
	}
	for (int i=L; i<R; i++) if (!mx[i]){
		vector<int> vec;
		int v=i;
		while (1){
			vec.pb(v);
			v=P[v];
			if (v==i) break ;
		}
		mn[i]=mx[i]=i;
		for (int v:vec){
			mn[i]=min(mn[i], v);
			mx[i]=max(mx[i], v);
		}
		for (int v:vec){
			mn[v]=mn[i];
			mx[v]=mx[i];
		}
	}
	// debug2(mn[3], mx[3])
	pii p=fix(s, s);
	int tl=p.first, tr=p.second;
	for (int i=L; i<tl; i++) if (!ps[i]){
		ans+=2;
		L=i+1;
	}
	for (int i=R-1; i>=tr; i--) if (!ps[i]){
		ans+=2;
		R=i;
	}
	// debug(ans)
	while (tr-tl!=R-L){
		int l=tl, r=tr;
		int cl=0, cr=0;
		while (L<l){
			cl+=2;
			pii p=fix(--l, tr);
			l=p.first;
			if (tr<p.second) break ;
		}
		while (r<R){
			cr+=2;
			pii p=fix(tl, ++r);
			r=p.second;
			if (p.first<tl) break ;
		}
		ans+=min(cl, cr);
		tl=l;
		tr=r;
	}
	
	return ans;
}

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