Submission #442118

#	Time	Username	Problem	Language	Result	Execution time	Memory
442118		prvocislo	Ancient Books (IOI17_books)	C++17	50 / 100	198 ms	26940 KiB

books

#include "books.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1e6 + 5;
vector<int> c(maxn, -1), L(maxn, maxn), R(maxn, -1);
void extend_for_free(int &l, int &r)
{
	int tl = min({l, L[c[l]], R[c[r]]}), tr = max({r, R[c[l]], R[c[r]]});
	while (tl < l || r < tr)
	{
		if (tl < l)
		{
			l--;
			tl = min(tl, L[c[l]]);
			tr = max(tr, R[c[l]]);
		}
		if (r < tr)
		{
			r++;
			tl = min(tl, L[c[r]]);
			tr = max(tr, R[c[r]]);
		}
	}
}
int calculate(int l, int r, int tl, int tr)
{
	int ans = 0;
	while (tl < l || r < tr)
	{
		extend_for_free(l, r);
		bool left = false, right = false;
		int cll = l, clr = r, crl = l, crr = r, costl = 0, costr = 0;
		while (tl < cll)
		{
			cll--, costl += 2;
			extend_for_free(cll, clr);
			if (clr > r) 
			{
				left = true; 
				break;
			}
		}
		while (tr > crr)
		{
			crr++, costr += 2;
			extend_for_free(crl, crr);
			if (crl < l) 
			{
				right = true; 
				break;
			}
		}
		if (left && right) ans += min(costl, costr);
		else ans += costl + costr;
		l = min(cll, crl), r = max(crl, crr);
	}
	return ans;
}
ll minimum_walk(vector<int> p, int s)
{
	int n = p.size(), num = -1, l = s, r = s;
	ll ans = 0;
	for (int i = 0; i < n; i++)
	{
		ans += abs(p[i] - i);
		if (c[i] != -1) continue;
		num++, L[num] = R[num] = i, c[i] = num;
		int j = p[i];
		while (j != i)
		{
			L[num] = min(L[num], j), R[num] = max(R[num], j), c[j] = num;
			j = p[j];
		}
		if (i != p[i]) l = min(l, L[num]), r = max(r, R[num]);
	}
	ans += calculate(s, s, l, r);
	return ans;
}

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