Submission #249737

#	Time	Username	Problem	Language	Result	Execution time	Memory
249737		kostia244	Ancient Books (IOI17_books)	C++17	50 / 100	284 ms	82808 KiB

books

#include "books.h"
#include<bits/extc++.h>
using namespace std;
const int maxn = 1<<20;
using ll = long long;
int vis[maxn], a[maxn], col[maxn], n, id = 0;
int L, R, pL, pR, rL = 1<<30, rR = -1<<30, left = 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);
	}
}

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);
	}
}
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(i == s || a[i] != i) {
			rR = max(rR, i);
			rL = min(rL, 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();
	while(L > rL || R < rR) {
		ans += 2;
		if(L > rL) pL--;
		else pR++;
		expand();
	}
	return ans;
}

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