Submission #390671

#	Time	Username	Problem	Language	Result	Execution time	Memory
390671		Keshi	Ancient Books (IOI17_books)	C++17	70 / 100	2090 ms	152632 KiB

books

//In the name of God
#include <bits/stdc++.h>
#include "books.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 1e6 + 100;
const ll lg = 20;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)

ll a[maxn], t, tt, c[maxn], rr[maxn], e[maxn];
ll b[maxn];
ll mn[maxn], mx[maxn], mnp[maxn], mxp[maxn];
bool vis[maxn];
vector<ll> vec, g[maxn];
vector<pll> v2;

ll seg[lg][maxn];

void bld(ll n){
	for(ll i = 0; i < n; i++){
		seg[0][i] = b[i];
	}
	for(ll j = 1; j < lg; j++){
		for(ll i = 0; i + (1 << j) <= n; i++){
			seg[j][i] = max(seg[j - 1][i], seg[j - 1][i + (1 << (j - 1))]);
		}
	}
}
ll get(ll l, ll r){
	ll f = e[r - l];
	return max(seg[f][l], seg[f][r - (1 << f)]);
}

ll sz[maxn], cnt[maxn];
bool val[maxn];

ll solve(ll v, ll s){
	ll x = -1;
	ll ans = 0;
	for(ll i = 0; i < Sz(g[v]); i++){
		ll u = g[v][i];
		if(mnp[u] <= s && s <= mxp[u]) x = i;
		if(mnp[v] == 0){
//			cout << "$ " << u << "    " << mnp[u] << " " << mxp[u] << "\n";
		}
		ans += solve(u, s);
		sz[v] += sz[u];
	}
	val[v] = (sz[v] == mxp[v] - mnp[v] + 1);
	if(x == -1 || mnp[v] > s || s > mxp[v]) return 0;
//	if(!val[g[v][x]]) cout << v << " [" << mnp[v] << ", " << mxp[v] << "]    ----->   " << ans << "\n";
	if(!val[g[v][x]]) return ans;
	ll j = 0;
	ll y = inf;
	ll o = mnp[g[v][x]];
	for(ll i = x; i--;){
		ll u = g[v][i];
		if(!val[u]) continue;
		j++;
		if(mxp[u] + 1 != o){
			y = min(y, j);
			break;
		}
		o = mnp[u];
	}
	y = min(y, j + 1);
	j = 0;
	o = mxp[g[v][x]];
	for(ll i = x + 1; i < Sz(g[v]); i++){
		ll u = g[v][i];
		if(!val[u]) continue;
		j++;
		if(mnp[u] != o + 1){
			y = min(y, j);
			break;
		}
		o = mxp[u];
	}
	y = min(y, j + 1);
//	cout << "# " << v << " [" << mnp[v] << ", " << mxp[v] << "]    ----->   ";
	if(mnp[v] == -1){
//		cout << ans + Sz(g[v]) - 1 << "\n";
		return ans + Sz(g[v]) - 1;
	}
//	cout << ans + y << "\n";
	return ans + y;
}

long long minimum_walk(vector<int> p, int s){
	for(ll i = 2; i < maxn; i++){
		e[i] = e[i / 2] + 1;
	}
	ll n = Sz(p);
	ll l = 0;
	while(l < n && p[l] == l) l++;
	ll r = n;
	while(r && p[r - 1] == r - 1) r--;
	if(r <= l) return 0;
	l = min(l, s);
	r = max(r, s + 1);
	mn[0] = -1;
	mx[0] = n;
	t++;
	long long ans = 0;
	for(ll i = l; i < r; i++){
		ans += abs(p[i] - i);
		if(!vis[i]){
			ll v = i;
			mn[t] = inf;
			mx[t] = -inf;
			do{
				cout.flush();
				vis[v] = 1;
				mx[t] = max(mx[t], v);
				mn[t] = min(mn[t], v);
				cnt[t]++;
				v = p[v];
			}while(v != i);
			rr[mx[t]] = t;
			b[mn[t]] = mx[t];
			t++;
		}
	}
	bld(n);
	for(ll i = 0; i < t; i++){
		v2.pb(Mp(mn[i], i));
	}
	for(pll i : v2){
		if(!vis[i.S]) continue;
		mnp[tt] = i.F;
		mxp[tt] = mx[i.S];
		sz[tt] = cnt[i.S];
		vis[i.S] = 0;
		while(true){
			ll x = get(mnp[tt], mxp[tt] + 1);
			if(!vis[rr[x]] || x <= mxp[tt]) break;
			mxp[tt] = x;
			sz[tt] += cnt[rr[x]];
			vis[rr[x]] = 0;
		}
		tt++;
	}
	vec.clear();
	v2.clear();
	ll root = -1;
	for(ll i = 0; i < tt; i++){
		if(mnp[i] == -1) root = i;
		v2.pb(Mp(mnp[i], i));
	}
	sort(all(v2));
	for(pll i : v2){
		if(vec.empty()){
			vec.pb(i.S);
			continue;
		}
		while(mxp[vec.back()] < i.F) vec.pop_back();
		g[vec.back()].pb(i.S);
		vec.pb(i.S);
	}
	ll xx = solve(root, s);
	ans += 2 * xx;

	return ans;
}

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