제출 #810759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810759		NothingXD	고대 책들 (IOI17_books)	C++17	0 / 100	1 ms	340 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e6 + 10;

int n, a[maxn], L[maxn], R[maxn];
bool vis[maxn];

ll solve(int l, int r, int tl, int tr){
	int ql = min(l, L[l]);
	int qr = min(r, R[r]);
	while(ql < l || qr > r){
		while(ql < l){
			l--;
			ql = min(ql, L[l]);
			qr = max(qr, R[l]);
		}
		while(qr > r){
			r++;
			ql = min(ql, L[r]);
			qr = max(qr, R[r]);
		}
	}
	//debug(l, r);
	ll ans = 0;
	while(l != tl || r != tr){
		int cntl = 0;
		bool markl = false;
		int idkl = l, idkr = r;
		int ql = l, qr = r;
		while(idkl > tl && qr == r){
			idkl--;
			cntl++;
			ql = min(ql, L[idkl]);
			qr = max(qr, R[idkl]);
	//		debug(idkl, idkr, 1);
			while(ql < idkl || qr > idkr){
				while(ql < idkl){
					idkl--;
					ql = min(ql, L[idkl]);
					qr = max(qr, R[idkl]);
				}
				while(idkr < qr){
					idkr++;
					ql = min(ql, L[idkr]);
					qr = max(qr, R[idkr]);
				}
	//			debug(idkl, idkr);
			}
		}
		if (qr != r) markl = true;
	//	debug(1);
		int cntr = 0;
		bool markr = false;
		idkl = l, idkr = r;
		int ql2 = l, qr2 = r;
	//	debug(idkr, tr);
		while(idkr < tr && ql2 == l){
			idkr++;
			cntr++;
			ql2 = min(ql2, L[idkr]);
			qr2 = max(qr2, R[idkr]);
	//		debug(idkl, idkr, 1);
			while(ql2 < idkl || qr2 > idkr){
				while(ql2 < idkl){
					idkl--;
					ql2 = min(ql2, L[idkl]);
					qr2 = max(qr2, R[idkl]);
				}
				while(idkr < qr2){
					idkr++;
					ql2 = min(ql2, L[idkr]);
					qr2 = max(qr2, R[idkr]);
				}
	//			debug(idkl, idkr);
			}
		}
		if (ql2 != l) markr = true;
	//	debug(markl, markr, cntl, cntr);
		if (markl && markr){
			if (cntl < cntr){
				l = ql;
				r = qr;
				ans += 2*cntl;
			}
			else{
				l = ql2;
				r = qr2;
				ans += 2*cntr;
			}
		}
		else{
			l = tl;
			r = tr;
			ans += 2*cntl + 2*cntr;
		}
	}
	return ans;
}

ll minimum_walk(vector<int> p, int s) {
	n = p.size();
	int mn = s, mx = s;
	ll ans = 0;
	for (int i = 0; i < n; i++){
		a[i] = p[i];
		if (a[i] != i){
			mn = min(mn, i);
			mx = max(mx, i);
		}
		ans += abs(a[i] - i);
	}
	for (int i = 0; i < n; i++){
		vector<int> tmp;
		int x = i;
		while(!vis[x]){
			vis[x] = true;
			tmp.push_back(x);
			x = a[x];
		}
	//	debug(i);
		//for (auto x: tmp) debug(x);
		sort(all(tmp));
		for (auto x: tmp){
			L[x] = tmp[0];
			R[x] = tmp.back();
	//		debug(x, L[x], R[x]);
		}
	}
	return ans + solve(s, s, mn, mx);
}

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