Submission #790692

#	Time	Username	Problem	Language	Result	Execution time	Memory
790692		ymm	Ancient Books (IOI17_books)	C++17	100 / 100	139 ms	23992 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 1e6+10;
bool vis[N];
int mn[N], mx[N];
int n;

void Do(const vector<int> &p, int i) {
	int x = i, y = i;
	vector<int> vec;
	while (!vis[i]) {
		vec.push_back(i);
		vis[i] = 1;
		x = min(x, i);
		y = max(y, i);
		i = p[i];
	}
	for (int j : vec) {
		mn[j] = x;
		mx[j] = y+1;
	}
}

int l, r, pl, pr;

void go() {
	while (l < pl || pr < r) {
		while (l < pl) {
			--pl;
			l = min(l, mn[pl]);
			r = max(r, mx[pl]);
		}
		while (pr < r) {
			l = min(l, mn[pr]);
			r = max(r, mx[pr]);
			++pr;
		}
	}
}
pii try_left() {
	int cl = l;
	int ans = 0;
	LoopR (i,0,l) {
		while (i < cl) {
			++ans;
			--cl;
		}
		if (mx[i] > r)
			return {ans, i};
		cl = min(cl, mn[i]);
	}
	return {INT_MAX, -1};
}
pii try_right() {
	int cr = r;
	int ans = 0;
	Loop (i,r,n) {
		while (cr <= i) {
			++ans;
			++cr;
		}
		if (mn[i] < l)
			return {ans, i};
		cr = max(cr, mx[i]);
	}
	return {INT_MAX, n};
}

void trim(vector<int> &p, int &s) {
	int p0 = 0, p1 = p.size()-1;
	while (p0 < s && p[p0] == p0)
		++p0;
	while (s < p1 && p[p1] == p1)
		--p1;
	vector<int> ans(p1-p0+1);
	Loop (i,p0,p1+1)
		ans[i-p0] = p[i]-p0;
	p = ans;
	s = s-p0;
}


long long minimum_walk(std::vector<int> p, int s) {
	trim(p, s);
	n = p.size();
	Loop (i,0,n) {
		if (!vis[i])
			Do(p, i);
	}
	ll ans = 0;
	l = s;
	r = s+1;
	pl = s;
	pr = s;
	go();
	for (;;) {
		auto [x, xi] = try_left();
		auto [y, yi] = try_right();
		//cerr << x << ' ' << y << '\n';
		if (x == INT_MAX && y == INT_MAX)
			break;
		if (x < y) {
			ans += x;
			l = xi;
		} else {
			ans += y;
			r = yi+1;
		}
		go();
	}
	while (0 < l) {
		--l;
		++ans;
		go();
	}
	while (r < n) {
		++r;
		++ans;
		go();
	}
	ans *= 2;
	Loop (i,0,n)
		ans += abs(i - p[i]);
	return ans;
}

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