Submission #47234

#	Time	Username	Problem	Language	Result	Execution time	Memory
47234		PowerOfNinjaGo	Ancient Books (IOI17_books)	C++17	100 / 100	274 ms	180012 KiB

books

//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
	#include "grader.cpp"
#else
	#include "books.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
int n;
const int maxn = 1e6+5;
vector<int> p;
int a[maxn], b[maxn];
ll dist[maxn];
bool vis[maxn];
int belong[maxn];
int cnt = 0;
void dfs(int u)
{
	if(vis[u]) return;
	vis[u] = true;
	belong[u] = cnt;
	a[cnt] = min(u, a[cnt]);
	b[cnt] = max(u, b[cnt]);
	dist[cnt] += abs(p[u]-u);
	dfs(p[u]);
}
void change(int &l, int &r)
{
	int ll = min(l, min(a[belong[l]], a[belong[r]]));
	int rr = max(r, max(b[belong[l]], b[belong[r]]));
	while(ll< l || r< rr)
	{
		if(ll< l)
		{
			l--;
			ll = min(ll, a[belong[l]]);
			rr = max(rr, b[belong[l]]);
		}
		else
		{
			r++;
			ll = min(ll, a[belong[r]]);
			rr = max(rr, b[belong[r]]);
		}
	}
}
int solve(int l, int r, int want_l, int want_r)
{
	int ret = 0;
	do
	{
		change(l, r);
		//cout << l << ' ' << r << endl;
		bool to_left = false;
		int costL = 0;
		int s_l = l, s_r = r;
		while(true)
		{
			if(s_l<= want_l) break;
			s_l--;
			costL += 2;
			change(s_l, s_r);
			if(s_r> r)
			{
				to_left = true;
				break;
			}
		}
		//cout << s_l << '?' << s_r << endl;
		bool to_right = false;
		int costR = 0;
		int k_l = l, k_r = r;
		while(true)
		{
			if(k_r>= want_r) break;
			k_r++;
			costR += 2;
			change(k_l, k_r);
			if(k_l< l)
			{
				to_right = true;
				break;
			}
		}
		if(to_left && to_right)
		{
			ret += min(costL, costR);
		}
		else
		{
			ret += costL + costR;
		}
		l = min(s_l, k_l);
		r = max(s_r, k_r);
	}
	while(want_l< l || r< want_r);
	return ret;
}
long long minimum_walk(std::vector<int> P, int s)
{
	p = P;
	n = P.size();
	for(int i = 0; i< n; i++) a[i] = 1e9;
	int l = s, r = s;
	ll res = 0;
	for(int i = 0; i< n; i++)
	{
		if(vis[i]) continue;
		dfs(i);
		res += dist[cnt];
		if(a[cnt] != b[cnt])
		{
			l = min(l, a[cnt]);
			r = max(r, b[cnt]);
		}
		cnt++;
	}
	//don't forget when s = 0
	return res+solve(s, s, l, r);
}

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