제출 #431821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431821		rainboy	Ancient Books (IOI17_books)	C++98	50 / 100	193 ms	13124 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], ii[N], m;

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

		while (j < k) {
			int c = ll_[ii[j]] - ll_[i_];

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

long long minimum_walk(vi pp, int s) {
	int n = pp.size(), h, 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];
			}
			xx[l]++, xx[r]--;
			if (l <= s && s <= r)
				ll_[m] = l_, rr_[m] = r_, ll[m] = l, rr[m] = r, ii[m] = i, m++;
		}
	}
	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];
	sort(ii, 0, m);
	cnt = 0;
	for (h = 0; h < m; h++) {
		i = ii[h];
		while (cnt && rr_[ii[cnt - 1]] < rr_[i]) {
			j = ii[--cnt];
			ll_[i] = max(ll_[i], ll_[j]), rr_[i] = min(rr_[i], rr_[j]);
			ll[i] = min(ll[i], ll[j]), rr[i] = max(rr[i], rr[j]);
		}
		ii[cnt++] = i;
	}
	for (h = cnt - 1, l_ = s, r_ = s; h >= 0; h--) {
		i = ii[h];
		if (l_ > ll_[i] && r_ < rr_[i])
			ans += min(xx[l_] - xx[ll_[i]], xx[rr_[i]] - xx[r_]) * 2;
		l_ = min(l_, ll[i]), r_ = max(r_, rr[i]);
	}
	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: 0 / 20
• Subtask 5: 0 / 30