Submission #118109

#	Time	Username	Problem	Language	Result	Execution time	Memory
118109		PeppaPig	Ancient Books (IOI17_books)	C++14	50 / 100	339 ms	30456 KiB

books

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

#define long long long

using namespace std;

const int N = 1e6+5;

int n, x, y;
int chk[N], id[N], L[N], R[N];
long ans;

void extend(int &l, int &r) {
	int ll = l, rr = r;
	ll = min(ll, min(L[id[l]], L[id[r]]));
	rr = max(rr, max(R[id[l]], R[id[r]]));

	while(ll < l || r < rr) {
		if(ll < l) --l;
		else ++r;
		ll = min(ll, min(L[id[l]], L[id[r]]));
		rr = max(rr, max(R[id[l]], R[id[r]]));
	}
}

long solve(int l, int r) {
	long ret = 0;
	while(x < l || r < y) {
		int a_l = l, a_r = r;
		int b_l = l, b_r = r;
		long cost_l = 0, cost_r = 0;
		bool valid_l = false, valid_r = false;
		while(x < a_l && a_r == r) {
			cost_l += 2;
			extend(--a_l, a_r);
		}
		if(a_r == y) valid_l = true;
		while(b_r < y && b_l == l) {
			cost_r += 2;
			extend(b_l, ++b_r);
		}
		if(valid_l && valid_r) ret += min(cost_l, cost_r);
		else ret += cost_l + cost_r;
		l = min(a_l, b_l), r = max(a_r, b_r);
		extend(l, r);
	}
	return ret;
}

long minimum_walk(vector<int> p, int s) {
	n = p.size(), x = y = s;

	for(int i = 0; i < n; i++) ans += abs(i - p[i]);
	for(int i = 0, ptr = 0; i < n; i++) if(!chk[i]) {
		int now = i;
		++ptr;
		L[ptr] = R[ptr] = i;
		while(!chk[now]) {
			chk[now] = true, id[now] = ptr;
			L[ptr] = min(L[ptr], now);
			R[ptr] = max(R[ptr], now);
			now = p[now];
		}
		if(i != p[i]) {
			x = min(x, L[ptr]);
			y = max(y, R[ptr]);
		}
	}

	int t_l = s, t_r = s;
	extend(t_l, t_r);
	return ans + solve(t_l, t_r);
}

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