Submission #249912

#	Time	Username	Problem	Language	Result	Execution time	Memory
249912		kostia244	Ancient Books (IOI17_books)	C++17	50 / 100	312 ms	76024 KiB

books

#include "books.h"
#include<bits/extc++.h>
using namespace std;
const int maxn = 1<<20;
using ll = long long;
#define end orz
int vis[maxn], a[maxn], col[maxn], n, id = 0;
vector<int> cycle[maxn];
ll ans = 0;
vector<array<int, 2>> segs;
void touch(int p) {
	if(vis[p]) return;
	++id;
	int l = p, r = p, lst = p;
	while(!vis[p]) {
		vis[p] = 1;
		l = min(l, p);
		r = max(r, p);
		
		col[p] = id;
		
		lst = p;
		p = a[p];
		ans += abs(p-lst);
	}
}
int L, R, pL, pR;
void upd(int i) {
	pL = min(pL, cycle[col[i]][0]);
	pR = max(pR, cycle[col[i]].back());
}
void expand() {
	while(pL < L || pR > R) {
		while(L > pL) upd(--L);
		while(R < pR) upd(++R);
	}
}
int start = -1, end = -1;
template<int fl>
pair<int, int> find() {
	int bl = L, br = R, cost = 0;
	//cout << fl << "::\n";
	//cout << cost << " " << L << " " << R << " TO " << endl;
	while((!fl ? L == bl : R == br) && (fl ? L>start : R!=end)) {
		fl ? --pL : ++pR;
		++cost;
		expand();
	}
	//cout << cost << " " << L << " " << R << endl;
	int nl = L, nr = R;
	pL = L = bl, R = pR = br;
	if(!fl ? L == nl : R == nr) return {1<<30, -1};
	return {cost, fl ? nl : nr};
}
ll minimum_walk(vector<int> _a, int s) {
	n = _a.size();
	for(int i = 0; i < n; i++) a[i] = _a[i];
	for(int i = 0; i < n; i++) {
		if(a[i] != i || i == s) {
			if(start == -1) start = i;
			end = i;
		}
		touch(i);
	}
	for(int i = 0; i < n; i++) cycle[col[i]].push_back(i);
	memset(vis, 0, sizeof vis);
	pL = pR = R = s, L = s+1;
	expand();
	//cout << start << " " << end << " " << L << " " << R << '\n';
	while(pL != start || pR != end) {
		if(pL == start) {
			pR++;
			ans += 2;
			expand();
			continue;
		}
		if(pR == end) {
			pL--;
			ans += 2;
			expand();
			continue;
		}
		auto [lcst, lp] = find<1>();
		auto [rcst, rp] = find<0>();
		//cout << lp << " " << rp << endl;
		if(lp == -1 && rp == -1) break;
		if(lcst < rcst) pL = lp;
		else pR = rp;
		ans += 2*min(lcst, rcst);
		expand();
	}
	return ans;
}

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