Submission #65781

#	Time	Username	Problem	Language	Result	Execution time	Memory
65781		MatheusLealV	Ancient Books (IOI17_books)	C++17	50 / 100	497 ms	112240 KiB

books

#include "books.h"
#define N 1000005
#define f first
#define ss second
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll ans = 0;

ll n, maior[N], menor[N], qtd = 0, ok[N], en;

int pai[N], peso[N];

int find(int x)
{
	if(x == pai[x]) return x;

	return pai[x] = find(pai[x]);
}

void join(int a, int b)
{
	a = find(a), b = find(b);

	if(a == b) return;

	if(peso[a] > peso[b]) pai[b] = a;

	else if(peso[a] < peso[b]) pai[a] = b;

	else pai[a] = b, peso[b] ++;
}

vector<int> g;

void dfs(ll x, ll &mx, ll &mn)
{
	mx = max(mx, maior[x]);

	if(ok[x]) return;

	ok[x] = 1;

	dfs(g[x], mx, mn);
}

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

	g = p;

	for(ll i = 0; i < n; i++) ans += abs(i - p[i]);

	for(int i = 0; i < n; i++) maior[i] = menor[i] = i;

	for(ll i = n - 1; i >= 0; i--)
	{
		if(p[i] != i)
		{
			en = i;

			break;
		}
	}

	vector<pii> sweep;

	for(int i = 0; i <= en; i++)
	{
		if(ok[i]) continue;

		dfs(i, maior[i], menor[i]);

		sweep.push_back({menor[i], maior[i]});
	}

	sort(sweep.begin(), sweep.end());

	for(int i = 0; i < (int)sweep.size(); i++) pai[i] = i;

	pii a = {-1, -1};

	for(int i = 0; i < (int)sweep.size(); i++)
	{
		auto b = sweep[i];


		if(b.f <= a.f) join(i, a.ss);

		a = max(a, {b.ss, i});

		//for(int j = 0; j < i; j++)
		//{
		//}
	}

	set<int> q;

	for(int i = 0; i < (int)sweep.size(); i++)
	{
		q.insert(find(i));
	}

	ll qtd = q.size();

	//cout<<q.size()<<"\n";

	return ans + 2*(qtd - 1);
}

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