Submission #1225475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225475		Hamed_Ghaffari	Ancient Books (IOI17_books)	C++20	100 / 100	114 ms	19784 KiB

books

#include <bits/stdc++.h>
using namespace std;

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

#define X first
#define Y second

const int MXN = 1e6+5;

int n, s, C, cmp[MXN], lc[MXN], rc[MXN], L, R, Lw, Rw;
vector<int> p;
ll ans;

void dfs(int v) {
	cmp[v] = C;
	lc[C] = min(lc[C], v);
	rc[C] = max(rc[C], v);
	if(!cmp[p[v]]) dfs(p[v]);
}

inline void extend() {
	while(L>Lw || R<Rw) {
		if(L>Lw) {
			L--;
			if(p[L]!=L) {
				Lw = min(Lw, lc[cmp[L]]);
				Rw = max(Rw, rc[cmp[L]]);
			}
		}
		if(R<Rw) {
			R++;
			if(p[R]!=R) {
				Lw = min(Lw, lc[cmp[R]]);
				Rw = max(Rw, rc[cmp[R]]);
			}
		}
	}
}

inline bool find() {
	extend();
	int L2 = -1;
	for(int i=L-1; i>=0; i--)
		if(p[i]!=i && rc[cmp[i]]>s) {
			L2 = i;
			break;
		}
	if(L2 == -1) return 0;
	int R2 = -1;
	for(int i=R+1; i<n; i++)
		if(p[i]!=i && lc[cmp[i]]<s) {
			R2 = i;
			break;
		}
	int cl=0, cr=0;
	int reserve = L;
	for(int i=L-1; i>=L2; i--) {
		if(reserve>i) cl += 2;
		if(p[i] != i) reserve = min(reserve, lc[cmp[i]]);
	}
	reserve = R;
	for(int i=R+1; i<=R2; i++) {
		if(reserve<i) cr += 2;
		if(p[i] != i) reserve = max(reserve, rc[cmp[i]]);
	}
	ans += min(cl, cr);
	Lw = L2;
	Rw = R2;
	return 1;
}

ll minimum_walk(vector<int> p, int s) {
	n = p.size();
	::p = p;
	::s = s;
	for(int i=0; i<n; i++)
		if(p[i]!=i) {
			ans += abs(p[i]-i);
			if(!cmp[i]) {
				C++;
				lc[C] = 1e9;
				rc[C] = -1e9;
				dfs(i);
			}
		}
	bool nont=0;
	int mx = 0;
	for(int i=0; i<s; i++) {
		nont |= p[i]!=i;
		mx = max(mx, p[i]);
		if(mx<=i && nont) ans += 2;
	}
	nont = 0;
	mx = n-1;
	for(int i=n-1; i>s; i--) {
		nont |= p[i] != i;
		mx = min(mx, p[i]);
		if(mx>=i && nont) ans += 2;
	}
	L=s; R=s;
	Lw = p[s]==s ? s : lc[cmp[s]];
	Rw = p[s]==s ? s : rc[cmp[s]];
	while(find());
	return ans;
}

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