Submission #355508

#	Time	Username	Problem	Language	Result	Execution time	Memory
355508		amunduzbaev	Ancient Books (IOI17_books)	C++14	100 / 100	369 ms	131692 KiB

books

#include "books.h"
 
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
 
#define ll long long
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
 
const ll inf = 1e9+7;
const int N = 1e6+5;
const int mod = 1e9+7;
 
int n, used[N], last, L[N], R[N], in[N];
int endL, endR;
map<pii, ll> dp;

void ext(int &l, int &r){
	int new_l = min(L[in[l]], L[in[r]]), new_r = max(R[in[r]], R[in[l]]);
	while(1){
		if(new_l < l) new_l = min(L[in[--l]], new_l), new_r = max(R[in[l]], new_r);
		else if(new_r > r) new_l = min(L[in[++r]], new_l), new_r = max(R[in[r]], new_r);
		else break;
	}//return {new_l, new_r};
}

ll fun(int l, int r){
	ext(l, r);
	if(l == endL && r == endR) return 0;
	if(dp.find(make_pair(l, r)) != dp.end()) return dp[make_pair(l, r)];
	if(l == endL) return dp[{l, r}] = fun(l, r+1)+2;
	if(r == endL) return dp[{l, r}] = fun(l-1, r)+2;
	
	
	int l_l = l-1, l_r = r;  ext(l_l, l_r);
	int r_l = l, r_r = r+1;  ext(r_l, r_r);
	int lans = 1, rans = 1;
	
	// trying to move our tmpl while our tmpr is < our extended {l, r+1} range
	
	while(l_l != endL && l_r < r_r){
		lans++, l_l--;
		ext(l_l, l_r);
	}if(l_r < r_r) return dp[{l, r}] = lans*2 + fun(l_l, l_r);
	
	// trying to move our tmpr while our tmpl is > our extended {l-1, r} range
	
	r_r = r+1, r_l = l; ext(r_l, r_r);
	l_l = l-1, l_r = r; ext(l_l, l_r);
	
	while(r_r != endR && r_l > l_l){
		rans++, r_r++;
		ext(r_l, r_r);
	}if(r_l > l_l) return dp[{l, r}] = rans*2 + fun(r_l, r_r);
	
	return dp[{l, r}] = min(lans, rans)*2 + fun(r_l, r_r);
}

ll minimum_walk(vector<int> p, int s) {
	//memset(dp, -1, sizeof dp);
	ll res = 0;
	endL = s, endR = s, n = sz(p);
	
	for(int i=0;i<n;i++){
		if(!used[i]){
			int u = i;
			L[last] = u, R[last] = u;
			do{
				used[u] = 1;
				in[u] = last;
				L[last] = min(L[last], u);
				R[last] = max(R[last], u);
				res += abs(p[u] - u);
				u = p[u];
			}while(u != i);
			if(L[last] != R[last]){
				endL = min(L[last], endL);
				endR = max(R[last], endR);
			}
			last++;
		}
	}
	
	return fun(s, s) + res;
}

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