Submission #431843

#	Time	Username	Problem	Language	Result	Execution time	Memory
431843		rainboy	Ancient Books (IOI17_books)	C++98	100 / 100	195 ms	26360 KiB

books

#include "books.h"
#include <string.h>

using namespace std;

const int N = 1000000;
const int INF = 0x3f3f3f3f;

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

typedef vector<int> vi;

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

char visited[N]; int xx[N], ll[N], rr[N], ll_[N], rr_[N], hh[N], m;

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = ll_[hh[j]] - ll_[h];

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

long long minimum_walk(vi pp, int s) {
	int n = pp.size(), h, h_, h1, i, j, l, r, l_, r_, cnt;
	long long ans;

	ans = 0;
	for (i = 0; i < n; i++) {
		if (i < pp[i])
			ans += pp[i] - i;
		else if (i > pp[i])
			ans += i - pp[i];
		if (!visited[i]) {
			l_ = -INF, r_ = INF, l = INF, r = -INF;
			while (!visited[i]) {
				l = min(l, i), r = max(r, i);
				if (i <= s)
					l_ = max(l_, i);
				if (i >= s)
					r_ = min(r_, i);
				visited[i] = 1, i = pp[i];
			}
			if (l <= s && s <= r)
				ll_[m] = l_, rr_[m] = r_, ll[m] = l, rr[m] = r, m++;
			else
				xx[l]++, xx[r]--;
		}
	}
	for (i = 1; i < n - 1; i++)
		xx[i] += xx[i - 1];
	for (i = n - 1; i > 0; i--)
		xx[i] = xx[i - 1] == 0;
	for (i = 1; i < n; i++)
		xx[i] += xx[i - 1];
	for (h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	cnt = 0;
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		while (cnt && rr_[hh[cnt - 1]] < rr_[h_]) {
			h1 = hh[--cnt];
			ll_[h_] = max(ll_[h_], ll_[h1]), rr_[h_] = min(rr_[h_], rr_[h1]);
			ll[h_] = min(ll[h_], ll[h1]), rr[h_] = max(rr[h_], rr[h1]);
		}
		hh[cnt++] = h_;
	}
	for (h = cnt - 1, l_ = s, r_ = s; h >= 0; h--) {
		h_ = hh[h];
		if (l_ > ll_[h_] && r_ < rr_[h_])
			ans += min(xx[l_] - xx[ll_[h_]], xx[rr_[h_]] - xx[r_]) * 2;
		l_ = min(l_, ll[h_]), r_ = max(r_, rr[h_]);
	}
	i = 0;
	while (i < l_ && pp[i] == i)
		i++;
	j = n - 1;
	while (j > r_ && pp[j] == j)
		j--;
	ans += (xx[l_] - xx[i] + xx[j] - xx[r_]) * 2;
	return ans;
}

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