Submission #271591

#	Time	Username	Problem	Language	Result	Execution time	Memory
271591		kdh9949	Ancient Books (IOI17_books)	C++17	100 / 100	1418 ms	123976 KiB

books

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

ll minimum_walk(vint p, int s) {
	int n = p.size();
	
	vint cnum(n), lp(1), rp(1);
	int cnt = 0;
	ll ans = 0;
	for(int i = 0; i < n; i++) {
		if(cnum[i] || p[i] == i) continue;
		cnt++;
		int x = i;
		lp.push_back(i);
		rp.push_back(i);
		do {
			ans += abs(x - p[x]);
			x = p[x];
			lp[cnt] = min(lp[cnt], x);
			rp[cnt] = max(rp[cnt], x);
			cnum[x] = cnt;
		} while(x != i);
	}

	int ls = s, rs = s;	
	vpii seg;
	for(int i = 1; i <= cnt; i++) seg.emplace_back(lp[i], rp[i]);
	sort(all(seg), [&](pii &p, pii &q){ return p.y > q.y; });
	for(pii &p : seg) if(ls <= p.y) ls = min(ls, p.x);
	sort(all(seg), [&](pii &p, pii &q){ return p.x < q.x; });
	for(pii &p : seg) if(p.x <= rs) rs = max(rs, p.y);

	vint d(n, n);
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	set<int> cand[2];
	for(int i = ls; i <= rs; i++) { cand[0].insert(i); cand[1].insert(i); }
	
	auto put = [&](int l, int r, int c, int a) {
		auto &cc = cand[a];
		auto it = cc.lower_bound(l);
		while(it != cc.end() && *it <= r) {
			int x = *it;
			it++;
			cc.erase(x);
			if(d[x] > c + a) {
				d[x] = c + a;
				pq.emplace(c + a, x);
			}
		}
	};
	
	put(s, s, 0, 0);
	while(!pq.empty()) {
		pii c = pq.top();
		pq.pop();
		if(d[c.y] != c.x) continue;
		if(c.y == ls || c.y == rs) {
			ans += 2 * c.x;
			break;
		}
		if(cnum[c.y]) put(lp[cnum[c.y]], rp[cnum[c.y]], c.x, 0);
		if(c.y > 0) put(c.y - 1, c.y - 1, c.x, 1);
		if(c.y < n - 1) put(c.y + 1, c.y + 1, c.x, 1);
	}

	vpii lseg;
	for(int i = 1; i <= cnt; i++) if(rp[i] < ls) lseg.emplace_back(lp[i], rp[i]);
	sort(all(lseg), [&](pii &p, pii &q){ return p.y > q.y; });
	for(pii &p : lseg) {
		if(p.y < ls) ans += 2 * (ls - p.y);
		ls = min(ls, p.x);
	}

	vpii rseg;
	for(int i = 1; i <= cnt; i++) if(rs < lp[i]) rseg.emplace_back(lp[i], rp[i]);
	sort(all(rseg), [&](pii &p, pii &q){ return p.x < q.x; });
	for(pii &p : rseg) {
		if(rs < p.x) ans += 2 * (p.x - rs);
		rs = max(rs, p.y);
	}

	return ans;
}

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