제출 #338159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
338159		pit4h	고대 책들 (IOI17_books)	C++14	0 / 100	35 ms	32236 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;
int segments[2][N];

bool overlap(int l1, int r1, int l2, int r2) {
	return (l1<l2 && r1>r2) || (l1>r2 && r1<l2);
}

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]);
	}
	
	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);
	}
	
	for(int i=0; i<n; ++i) {
		segments[0][i] = segments[1][i] = i;
	}
	
	for(int i=0; i<n; ++i) {
		if(dsu.Find(i)==i && dsu.getl(i)!=dsu.getr(i)) {
			segments[0][dsu.getl(i)] = dsu.getr(i);
			segments[1][dsu.getr(i)] = dsu.getl(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--;
	}

	ll ANS = ans;
	vector<int> st;
	for(int i=0; i<n; ++i) {
		if(dsu.getl(i)==dsu.getr(i)) continue;
		if(dsu.getl(i)==i) st.push_back(dsu.Find(i));
		if(dsu.getr(i)==i) {
			assert(st.back()==dsu.Find(i));
			st.pop_back();
		}
		if(i>=le && i<ri) {
			if(st.empty()) ANS+=2;
		}
	}

	int pos[2] = {dsu.getl(s), dsu.getr(s)}, move[2] = {-1, 1};

	int iter=0;
	while(pos[0]>le || pos[1]<ri) {
		iter++;
		int cost[2] = {0, 0}, lim[2] = {pos[0], pos[1]};	
		pos[0]--; pos[1]++;
		for(int dir=0; dir<2; ++dir) {
			while(pos[dir]>=le && pos[dir]<=ri && !overlap(pos[dir], segments[dir][pos[dir]], lim[0], lim[1]) ) {
				cost[dir] -= abs(pos[dir] - segments[dir][pos[dir]]);
				pos[dir] += move[dir];
			}
		}
		pos[0] = max(pos[0], le), pos[1] = min(pos[1], ri);
		cost[0] += lim[0] - pos[0];
		cost[1] += pos[1] - lim[1];
		if(segments[0][pos[0]] == pos[1]) {
			ans += min(cost[0], cost[1]) * 2;
		}
		else {
			ans += (cost[0] + cost[1]) * 2;
		}
	}
	assert(s!=0 || iter<=1);
	assert(s!=0 || ans==ANS);
	return ans;
}

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