Submission #105260

#	Time	Username	Problem	Language	Result	Execution time	Memory
105260		bert30702	Ancient Books (IOI17_books)	C++17	70 / 100	2044 ms	255416 KiB

books

#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
#include "books.h"
using namespace std;
const int MX = 1e6 + 100;
pii v[MX];
int mn[MX], mx[MX], tmpn[MX], tmpx[MX];
unordered_map<int, int> dp[MX];
int dfs(int l, int r, int a, int b) {
	// cout << l << ' ' << r << ' ' << a << ' ' << b << endl;
	if(l == a and r == b) return 0;
	if(dp[l].find(r) != dp[l].end()) return dp[l][r];
	if(l == a) return 2 + dfs(l, v[r + 1].S, a, b);
	if(r == b) return 2 + dfs(v[l - 1].F, r, a, b);
	int l1 = min(v[l - 1].F, l);
	int r1 = max(v[l - 1].S, r);
	int l2 = min(v[r + 1].F, l);
	int r2 = max(v[r + 1].S, r);
	return dp[l][r] = 2 + min(dfs(l1, r1, a, b), dfs(l2, r2, a, b));
}
long long minimum_walk(vector<int> p, int s) {
	int x = 0, y = p.size() - 1;
	while(x < s and p[x] == x) x ++;
	while(y > s and p[y] == y) y --;
	for(int i = x; i <= y; i ++) mn[i] = mx[i] = i;
	for(int i = x; i <= y; i ++) {
		mn[i] = min(mn[i], p[i]);
		mx[i] = max(mx[i], p[i]);
		mn[p[i]] = min(mn[p[i]], i);
		mx[p[i]] = max(mx[p[i]], i);
	}
	long long sum = 0;
	for(int i = x; i <= y; i ++) sum += abs(p[i] - i);
	auto update = [&] (int p, int a) {
		mn[p] = min(mn[p], mn[a]);
		mx[p] = max(mx[p], mx[a]);	
	};
	{
		memcpy(tmpn, mn, sizeof(mn));
		memcpy(tmpx, mx, sizeof(mx));
		queue<int> a, b;
		for(int i = s - 1; i >= x; i --) a.push(i);
		for(int i = s + 1; i <= y; i ++) b.push(i);
		for(int i = s; i <= y; i ++) {
			while(1) {
					 if(a.size() and a.front() >= mn[i]) update(i, a.front()), a.pop();
				else if(b.size() and b.front() <= mx[i]) update(i, b.front()), b.pop();
				else break;
			}
			v[i] = {mn[i], mx[i]};
			i = mx[i]; 
		}
		memcpy(mn, tmpn, sizeof(mn));
		memcpy(mx, tmpx, sizeof(mx));
	}
	{
		memcpy(tmpn, mn, sizeof(mn));
		memcpy(tmpx, mx, sizeof(mx));
		queue<int> a, b;
		for(int i = s - 1; i >= x; i --) a.push(i);
		for(int i = s + 1; i <= y; i ++) b.push(i);
		for(int i = s; i >= x; i --) {
			while(1) {
					 if(a.size() and a.front() >= mn[i]) update(i, a.front()), a.pop();
				else if(b.size() and b.front() <= mx[i]) update(i, b.front()), b.pop();
				else break;
			}
			v[i] = {mn[i], mx[i]};
			i = mn[i];
		}
		memcpy(mn, tmpn, sizeof(mn));
		memcpy(mx, tmpx, sizeof(mx));
	}
	for(int i = x; i <= y; i ++) {
		// cout << i << ' ' << v[i].F << ' ' << v[i].S << endl;
	}
	// exit(0);
	return sum + dfs(v[s].F, v[s].S, x, y);
}

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