Submission #153278

#	Time	Username	Problem	Language	Result	Execution time	Memory
153278		mieszko11b	Ancient Books (IOI17_books)	C++14	12 / 100	3 ms	632 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ii = pair<int, int>;

#define X first
#define Y second

int n;
bool vis[1000007];
ii I[1000007];
int minv[21][1000007], maxv[21][1000007];
int maxk[1000007];

int getmin(int a, int b) {
	int l = (b - a + 1);
	return min(minv[maxk[l]][a], minv[maxk[l]][b - (1 << maxk[l]) + 1]);
}

int getmax(int a, int b) {
	int l = (b - a + 1);
	return max(maxv[maxk[l]][a], maxv[maxk[l]][b - (1 << maxk[l]) + 1]);
}

ii extend(int a, int b) {
	int na = min(a, getmin(a, b));
	int nb = max(b, getmax(a, b));
	if((ii){na, nb} == (ii){a, b})
		return {a, b};
	return extend(na, nb);
}

int dist_left(int x, int y) {
	if(x <= y)
		return 0;
	if(I[x].X < x)
		return dist_left(I[x].X, y);
	return 1 + dist_left(x - 1, y);
}

int dist_right(int x, int y) {
	if(x >= y)
		return 0;
	if(I[x].Y > x)
		return dist_right(I[x].Y, y);
	return 1 + dist_right(x + 1, y);
}

long long minimum_walk(std::vector<int> p, int s) {
	ll res = 0;
	n = p.size();

	for(int i = 0 ; i < n ; i++) {
		if(vis[i])
			continue;
	
		vector<int> tmp;
		int minx = 1e9, maxx = -1;
		
		int w = i;
		while(!vis[w]) {
			vis[w] = 1;
			res += abs(p[w] - w);
			minx = min(minx, w);
			maxx = max(maxx, w);
			tmp.push_back(w);
			w = p[w];
		}
		
		for(int x : tmp)
			I[x] = {minx, maxx};
	}

	for(int i = 0 ; i < n ; i++)
		minv[0][i] = maxv[0][i] = p[i];
		
	for(int k = 1 ; k < 20 ; k++) {
		for(int i = 0 ; i + (1 << k) <= n ; i++) {
			minv[k][i] = min(minv[k - 1][i], minv[k - 1][i + (1 << (k - 1))]);
			maxv[k][i] = max(maxv[k - 1][i], maxv[k - 1][i + (1 << (k - 1))]);
		}
	}
	
	int k = 0;
	for(int i = 1 ; i <= n ; i++) {
		if((1 << (k + 1)) <= i)
			k++;
		maxk[i] = k;
	}
	
	int begin = 0;
	while(begin < n && p[begin] == begin)
		begin++;
		
	if(begin == n)
		return 0;
		
	int end = n - 1;
	while(p[end] == end)
		end--;
	
	int a = extend(s, s).X, b = extend(s, s).Y;
	while(a > begin || b < end) {
		int lbook = a - 1;
		while(lbook >= 0 && I[lbook].Y < s)
			lbook--;

		if(lbook == -1) {
			res += 2 * dist_left(a, begin);
			res += 2 * dist_right(b, end);
			a = begin;
			b = end;
			continue;
		}
		
		int rbook = b + 1;
		while(I[rbook].X > s)
			rbook++;
			
		if(dist_left(a, lbook) < dist_right(b, rbook)) {
			res += 2 * dist_left(a, lbook);
		} else {
			res += 2 * dist_right(b, rbook);
		}
		
		ii r = extend(lbook, rbook);
		a = r.X;
		b = r.Y;
	}

	//~ for(int i = 0 ; i < n ; i++)
		//~ cout << I[i].X << " " << I[i].Y << endl;

	return res;
}

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