Submission #137810

#	Time	Username	Problem	Language	Result	Execution time	Memory
137810		random0029	Ancient Books (IOI17_books)	C++14	50 / 100	263 ms	36436 KiB

books

// ItnoE
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000006;
int n, M[N], A[N], MN[N * 2], MX[N * 2];
inline void Set(int i, int val)
{
	i += n;
	MN[i] = MX[i] = val;
	for (; i; i >>= 1)
	{
		MN[i >> 1] = min(MN[i], MN[i ^ 1]);
		MX[i >> 1] = max(MX[i], MX[i ^ 1]);
	}
}
inline pair < int , int > Get(int l, int r)
{
	r ++;
	l += n; r += n;
	pair < int , int > ret = {INT_MAX, INT_MIN};
	for (; l < r; l >>= 1, r >>= 1)
	{
		if (l & 1)
		{
			ret.first = min(ret.first, MN[l]);
			ret.second = max(ret.second, MX[l]);
			l ++;
		}
		if (r & 1)
		{
			r --;
			ret.first = min(ret.first, MN[r]);
			ret.second = max(ret.second, MX[r]);
		}
	}
	return (ret);
}
int64_t minimum_walk(vector < int > P, int st)
{
	n = (int)P.size();
	ll SM = 0;
	for (int i = 0; i < n; i ++)
		SM += abs(P[i] - i), Set(i, P[i]);
	vector < pair < int , int > > cyc;
	for (int i = 0; i < n; i ++)
		if (!M[i] && P[i] != i)
		{
			int v = i;
			int Mx = -N * 2, Mn = N * 2;
			while (!M[v])
			{
				M[v] = 1;
				Mn = min(Mn, v);
				Mx = max(Mx, v);
				v = P[v];
			}
			A[Mn] = max(A[Mn], Mx);
			cyc.push_back({Mn, Mx});
		}
	if (SM == 0)
		return (SM);
	//bool fail = 1;
	int Mx = 0, last = -1;
	vector < pair < int , int > > vec;
	for (int i = 0; i < n; i ++)
	{
		Mx = max({Mx, A[i], i});
		if (P[i] != i && last == -1)
			last = i;
		if (P[i] == i)
			continue;
		if (Mx == i)
			vec.push_back({last, Mx}), last = -1;
		//if (i <= st && st <= Mx)
			//fail = 0;
	}
	if (P[st] == st)
	{
		int le = st, ri = st;
		while (le >= 0 && P[le] == le)
			le --;
		while (ri < n && P[ri] == ri)
			ri ++;
		if (le == -1) le = st;
		if (ri == n) ri = st;
		SM += (ri - le) * 2;
	}
	else
	{
		pair < int , int > X;
		for (auto Y : vec)
			if (Y.first <= st && st <= Y.second)
				X = Y;
		int le = st, ri = st;
		int tole = st, tori = st;
		while (X != make_pair(le, ri))
		{
			while (1)
			{
				auto ff = Get(le, ri);
				if (le <= ff.first && ff.second <= ri)
					break;
				le = min(ff.first, le);
				ri = max(ff.second, ri);
			}
			tole = le - 1;
			tori = ri + 1;
			if (X.first == le && X.second == ri)
				break;
			while (tole >= X.first && P[tole] == tole)
				tole --;
			while (tori <= X.second && P[tori] == tori)
				tori ++;
			SM += (le - tole) * 2;
			SM += (tori - ri) * 2;
			le = max(tole, X.first);
			ri = min(tori, X.second);
		}
	}
	/*if (st != 0 && P[st] != st)
	{
		pair < int , int > X;
		for (auto Y : vec)
			if (Y.first <= st && st <= Y.second)
				X = Y;
		SM += min(st - X.first, X.second - st) * 2;
	}*/
	for (int i = 1; i < (int)vec.size(); i ++)
	{
		SM += (vec[i].first - vec[i - 1].second) * 2;
		assert(vec[i].first > vec[i - 1].second);
	}
	return (SM);
}

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