Submission #338227

#	Time	Username	Problem	Language	Result	Execution time	Memory
338227		pit4h	Ancient Books (IOI17_books)	C++14	100 / 100	295 ms	34780 KiB

books

#include "books.h"
#include "bits/stdc++.h"
#define st first
#define nd second
#define mp make_pair
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e6+1;
struct DSU {
	int f[N], cnt[N], l[N], r[N];
	DSU() {
		for(int i=0; i<N; ++i) {
			f[i] = l[i] = r[i] = i;
			cnt[i] = 1;
		}
	}
	int Find(int x) {
		if(f[x]==x) return x;
		f[x] = Find(f[x]);
		return f[x];
	}
	void Union(int x, int y) {
		x = Find(x), y = Find(y);
		if(x==y) return;
		if(cnt[x] < cnt[y]) swap(x, y);
		cnt[x] += cnt[y];
		l[x] = min(l[x], l[y]);
		r[x] = max(r[x], r[y]);
		f[y] = x;
	}
	int getl(int x) { return l[Find(x)]; }
	int getr(int x) { return r[Find(x)]; }
};
DSU dsu;

ll minimum_walk(vector<int> p, int s) {
	int n = p.size();
	ll ans = 0;
	for(int i=0; i<n; ++i) {
		ans += abs(p[i] - i);
		dsu.Union(i, p[i]);
	}
	//cerr<<ans<<'\n';

	vector<int> vec;
	for(int i=n-1; i>=0; --i) {
		while(vec.size() && dsu.getr(i) >= vec.back()) {
			if(dsu.getl(vec.back()) < i) {
				dsu.Union(i, vec.back());
			}
			vec.pop_back();
		}
		vec.push_back(i);
	}
	
	int le=0, ri=n-1;
	while(le<s && dsu.getl(le)==dsu.getr(le)) {
		le++;
	}
	while(ri>s && dsu.getl(ri)==dsu.getr(ri)) {
		ri--;
	}
	
	while(true) {
		int l=le, r=ri, cur=-1;
		int cost1=0, cost2=0;
		for(int i=dsu.getl(s)-1; i>=le; --i) {
			if(dsu.getr(i) > s) {
				l = i;	
				cur = dsu.Find(i);
				break;
			}
		}
		for(int i=dsu.getr(s)+1; i<=ri; ++i) {
			if(dsu.getl(i) < s) {
				r = i;
				break;
			}
		}
		if(cur!=-1) l++, cost1++;
		for(int i=l; i<dsu.getl(s); ++i) {
			cost1++;
			i = dsu.getr(i);
		}
		if(cur!=-1) r--, cost2++;
		for(int i=r; i>dsu.getr(s); --i) {
			cost2++;
			i = dsu.getl(i);
		}
		if(cur==-1) {
			ans += (cost1+cost2)*2;	
			break;
		}
		ans += min(cost1, cost2)*2;
		dsu.Union(cur, s);
	}
	return ans;
}

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