Submission #152382

#	Time	Username	Problem	Language	Result	Execution time	Memory
152382		qkxwsm	Ancient Books (IOI17_books)	C++14	100 / 100	253 ms	30712 KiB

books

#include <bits/stdc++.h>
 
using namespace std;
 
template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}
 
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 1000013
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
int N, S;
pii need = {-1, -1}, cur;
int dsu[MAXN];
pii range[MAXN];
vi arr;
ll ans;
 
int get(int u)
{
	return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
bool merge(int u, int v)
{
	u = get(u); v = get(v);
	if (u == v) return false;
	dsu[v] = u;
	ckmin(range[u].fi, range[v].fi);
	ckmax(range[u].se, range[v].se);
	return true;
}
 
ll minimum_walk(vi perm, int s)
{
	//mark all the blocks
	N = SZ(perm); S = s; arr = perm;
	FOR(i, 0, N)
	{
		dsu[i] = i;
		range[i] = {i, i};
	}
	FOR(i, 0, N)
	{
		merge(i, arr[i]);
	}
	//so we have access to (l..r).
	//what do we do? we constantly try to "expand" acess until we covered the entire needy range
	FOR(i, 0, N)
	{
		if (arr[i] != i)
		{
			need.fi = i;
			break;
		}
	}
	FORD(i, N, 0)
	{
		if (arr[i] != i)
		{
			need.se = i;
			break;
		}
	}
	if (need.fi == -1) return 0ll;
	ckmin(need.fi, S);
	ckmax(need.se, S);
	//implement the extend function? so for (l..r) you wanna be able to say basically the entire range that you get for free.
	int lt = range[get(S)].fi, rt = range[get(S)].se;
	cur = {S, S};
	while(cur.fi > lt || cur.se < rt)
	{
		for (int i = cur.fi - 1; i >= lt; i--)
		{
			ckmin(lt, range[get(i)].fi);
			ckmax(rt, range[get(i)].se);
		}
		cur.fi = lt;
		for (int i = cur.se + 1; i <= rt; i++)
		{
			ckmin(lt, range[get(i)].fi);
			ckmax(rt, range[get(i)].se);
		}
		cur.se = rt;
	}
	// cerr << cur.fi << ' ' << cur.se << ' ' << need.fi << ' ' << need.se << endl;
	while(cur != need)
	{
		//you need to expand the rnage at minimum cost.
		//find the first range you get
		ll lc = 0, rc = 0;
		int bound = cur.fi;
		for (lt = cur.fi - 1; lt >= need.fi; lt--)
		{
			//see if you get a new guy.
			if (bound == lt + 1) lc += 2;
			pii p = range[get(lt)];
			if (p.se > cur.se) break;
			ckmin(bound, p.fi);
		}
		bound = cur.se;
		for (rt = cur.se + 1; rt <= need.se; rt++)
		{
			if (bound == rt - 1) rc += 2;
			pii p = range[get(rt)];
			if (p.fi < cur.fi) break;
			ckmax(bound, p.se);
		}
		// cerr << "lc " << lc << " rc " << rc << endl;
		if (lt == need.fi - 1)
		{
			assert(rt == need.se + 1);
			ans += lc;
			ans += rc;
			cur = need;
			break;
		}
		ans += min(lc, rc);
		//ok now expand the range.
		while(cur.fi > lt || cur.se < rt)
		{
			for (int i = cur.fi - 1; i >= lt; i--)
			{
				ckmin(lt, range[get(i)].fi);
				ckmax(rt, range[get(i)].se);
			}
			cur.fi = lt;
			for (int i = cur.se + 1; i <= rt; i++)
			{
				ckmin(lt, range[get(i)].fi);
				ckmax(rt, range[get(i)].se);
			}
			cur.se = rt;
		}
	}
	FOR(i, 0, N)
	{
		ans += abs(arr[i] - i);
	}
	return ans;
}

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