oj.uz

Submission #390692

# Submission time Handle Problem Language Result Execution time Memory
390692 2021-04-16T14:15:27 Z Keshi Ancient Books (IOI17_books) C++17
100 / 100
 458 ms 294704 KB 
//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 = 2e6 + 100;
const ll lg = 22;
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){
	if(l < 0) l = 0;
	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);
	v2.reserve(n);
	vec.reserve(n);
	for(ll i = 0; i < n; i++){
		g[i].reserve(20);
	}
	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));
	}
	fill(vis, vis + maxn, 0);
	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]] = 1;
		}
		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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 57064 KB Output is correct
2 Correct 39 ms 57028 KB Output is correct
3 Correct 38 ms 57036 KB Output is correct
4 Correct 38 ms 57052 KB Output is correct
5 Correct 37 ms 57164 KB Output is correct
6 Correct 77 ms 57104 KB Output is correct
7 Correct 38 ms 57124 KB Output is correct
8 Correct 39 ms 57044 KB Output is correct
9 Correct 37 ms 55080 KB Output is correct
10 Correct 37 ms 57028 KB Output is correct
11 Correct 37 ms 55092 KB Output is correct
12 Correct 70 ms 57092 KB Output is correct
13 Correct 39 ms 57108 KB Output is correct
14 Correct 36 ms 55116 KB Output is correct
15 Correct 40 ms 57116 KB Output is correct
16 Correct 39 ms 57100 KB Output is correct
17 Correct 38 ms 57120 KB Output is correct
18 Correct 79 ms 57076 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 57064 KB Output is correct
2 Correct 39 ms 57028 KB Output is correct
3 Correct 38 ms 57036 KB Output is correct
4 Correct 38 ms 57052 KB Output is correct
5 Correct 37 ms 57164 KB Output is correct
6 Correct 77 ms 57104 KB Output is correct
7 Correct 38 ms 57124 KB Output is correct
8 Correct 39 ms 57044 KB Output is correct
9 Correct 37 ms 55080 KB Output is correct
10 Correct 37 ms 57028 KB Output is correct
11 Correct 37 ms 55092 KB Output is correct
12 Correct 70 ms 57092 KB Output is correct
13 Correct 39 ms 57108 KB Output is correct
14 Correct 36 ms 55116 KB Output is correct
15 Correct 40 ms 57116 KB Output is correct
16 Correct 39 ms 57100 KB Output is correct
17 Correct 38 ms 57120 KB Output is correct
18 Correct 79 ms 57076 KB Output is correct
19 Correct 40 ms 57276 KB Output is correct
20 Correct 38 ms 57348 KB Output is correct
21 Correct 36 ms 55160 KB Output is correct
22 Correct 59 ms 57340 KB Output is correct
23 Correct 38 ms 57284 KB Output is correct
24 Correct 40 ms 57368 KB Output is correct
25 Correct 38 ms 57280 KB Output is correct
26 Correct 38 ms 57348 KB Output is correct
27 Correct 39 ms 57268 KB Output is correct
28 Correct 40 ms 57340 KB Output is correct
29 Correct 37 ms 57344 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 57064 KB Output is correct
2 Correct 39 ms 57028 KB Output is correct
3 Correct 38 ms 57036 KB Output is correct
4 Correct 38 ms 57052 KB Output is correct
5 Correct 37 ms 57164 KB Output is correct
6 Correct 77 ms 57104 KB Output is correct
7 Correct 38 ms 57124 KB Output is correct
8 Correct 39 ms 57044 KB Output is correct
9 Correct 37 ms 55080 KB Output is correct
10 Correct 37 ms 57028 KB Output is correct
11 Correct 37 ms 55092 KB Output is correct
12 Correct 70 ms 57092 KB Output is correct
13 Correct 39 ms 57108 KB Output is correct
14 Correct 36 ms 55116 KB Output is correct
15 Correct 40 ms 57116 KB Output is correct
16 Correct 39 ms 57100 KB Output is correct
17 Correct 38 ms 57120 KB Output is correct
18 Correct 79 ms 57076 KB Output is correct
19 Correct 40 ms 57276 KB Output is correct
20 Correct 38 ms 57348 KB Output is correct
21 Correct 36 ms 55160 KB Output is correct
22 Correct 59 ms 57340 KB Output is correct
23 Correct 38 ms 57284 KB Output is correct
24 Correct 40 ms 57368 KB Output is correct
25 Correct 38 ms 57280 KB Output is correct
26 Correct 38 ms 57348 KB Output is correct
27 Correct 39 ms 57268 KB Output is correct
28 Correct 40 ms 57340 KB Output is correct
29 Correct 37 ms 57344 KB Output is correct
30 Correct 387 ms 234668 KB Output is correct
31 Correct 354 ms 233668 KB Output is correct
32 Correct 252 ms 157056 KB Output is correct
33 Correct 430 ms 266148 KB Output is correct
34 Correct 415 ms 266456 KB Output is correct
35 Correct 419 ms 261280 KB Output is correct
36 Correct 377 ms 250088 KB Output is correct
37 Correct 353 ms 242652 KB Output is correct
38 Correct 343 ms 240644 KB Output is correct
39 Correct 388 ms 240168 KB Output is correct
40 Correct 344 ms 235864 KB Output is correct
41 Correct 340 ms 234004 KB Output is correct
42 Correct 344 ms 234344 KB Output is correct
43 Correct 435 ms 265516 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 57400 KB Output is correct
2 Correct 39 ms 57360 KB Output is correct
3 Correct 38 ms 57284 KB Output is correct
4 Correct 44 ms 57260 KB Output is correct
5 Correct 39 ms 57396 KB Output is correct
6 Correct 37 ms 57268 KB Output is correct
7 Correct 38 ms 57280 KB Output is correct
8 Correct 38 ms 57352 KB Output is correct
9 Correct 39 ms 57352 KB Output is correct
10 Correct 36 ms 55108 KB Output is correct
11 Correct 45 ms 57368 KB Output is correct
12 Correct 38 ms 57316 KB Output is correct
13 Correct 38 ms 57348 KB Output is correct
14 Correct 38 ms 57304 KB Output is correct
15 Correct 38 ms 57364 KB Output is correct
16 Correct 38 ms 57284 KB Output is correct
17 Correct 37 ms 57360 KB Output is correct
18 Correct 39 ms 57296 KB Output is correct
19 Correct 38 ms 57292 KB Output is correct
20 Correct 38 ms 57284 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 57064 KB Output is correct
2 Correct 39 ms 57028 KB Output is correct
3 Correct 38 ms 57036 KB Output is correct
4 Correct 38 ms 57052 KB Output is correct
5 Correct 37 ms 57164 KB Output is correct
6 Correct 77 ms 57104 KB Output is correct
7 Correct 38 ms 57124 KB Output is correct
8 Correct 39 ms 57044 KB Output is correct
9 Correct 37 ms 55080 KB Output is correct
10 Correct 37 ms 57028 KB Output is correct
11 Correct 37 ms 55092 KB Output is correct
12 Correct 70 ms 57092 KB Output is correct
13 Correct 39 ms 57108 KB Output is correct
14 Correct 36 ms 55116 KB Output is correct
15 Correct 40 ms 57116 KB Output is correct
16 Correct 39 ms 57100 KB Output is correct
17 Correct 38 ms 57120 KB Output is correct
18 Correct 79 ms 57076 KB Output is correct
19 Correct 40 ms 57276 KB Output is correct
20 Correct 38 ms 57348 KB Output is correct
21 Correct 36 ms 55160 KB Output is correct
22 Correct 59 ms 57340 KB Output is correct
23 Correct 38 ms 57284 KB Output is correct
24 Correct 40 ms 57368 KB Output is correct
25 Correct 38 ms 57280 KB Output is correct
26 Correct 38 ms 57348 KB Output is correct
27 Correct 39 ms 57268 KB Output is correct
28 Correct 40 ms 57340 KB Output is correct
29 Correct 37 ms 57344 KB Output is correct
30 Correct 387 ms 234668 KB Output is correct
31 Correct 354 ms 233668 KB Output is correct
32 Correct 252 ms 157056 KB Output is correct
33 Correct 430 ms 266148 KB Output is correct
34 Correct 415 ms 266456 KB Output is correct
35 Correct 419 ms 261280 KB Output is correct
36 Correct 377 ms 250088 KB Output is correct
37 Correct 353 ms 242652 KB Output is correct
38 Correct 343 ms 240644 KB Output is correct
39 Correct 388 ms 240168 KB Output is correct
40 Correct 344 ms 235864 KB Output is correct
41 Correct 340 ms 234004 KB Output is correct
42 Correct 344 ms 234344 KB Output is correct
43 Correct 435 ms 265516 KB Output is correct
44 Correct 38 ms 57400 KB Output is correct
45 Correct 39 ms 57360 KB Output is correct
46 Correct 38 ms 57284 KB Output is correct
47 Correct 44 ms 57260 KB Output is correct
48 Correct 39 ms 57396 KB Output is correct
49 Correct 37 ms 57268 KB Output is correct
50 Correct 38 ms 57280 KB Output is correct
51 Correct 38 ms 57352 KB Output is correct
52 Correct 39 ms 57352 KB Output is correct
53 Correct 36 ms 55108 KB Output is correct
54 Correct 45 ms 57368 KB Output is correct
55 Correct 38 ms 57316 KB Output is correct
56 Correct 38 ms 57348 KB Output is correct
57 Correct 38 ms 57304 KB Output is correct
58 Correct 38 ms 57364 KB Output is correct
59 Correct 38 ms 57284 KB Output is correct
60 Correct 37 ms 57360 KB Output is correct
61 Correct 39 ms 57296 KB Output is correct
62 Correct 38 ms 57292 KB Output is correct
63 Correct 38 ms 57284 KB Output is correct
64 Correct 439 ms 267144 KB Output is correct
65 Correct 448 ms 270020 KB Output is correct
66 Correct 353 ms 249024 KB Output is correct
67 Correct 336 ms 248244 KB Output is correct
68 Correct 72 ms 75924 KB Output is correct
69 Correct 67 ms 75288 KB Output is correct
70 Correct 71 ms 76100 KB Output is correct
71 Correct 74 ms 77300 KB Output is correct
72 Correct 75 ms 78148 KB Output is correct
73 Correct 66 ms 74516 KB Output is correct
74 Correct 428 ms 272740 KB Output is correct
75 Correct 434 ms 272604 KB Output is correct
76 Correct 451 ms 271428 KB Output is correct
77 Correct 446 ms 271664 KB Output is correct
78 Correct 421 ms 268100 KB Output is correct
79 Correct 420 ms 268100 KB Output is correct
80 Correct 250 ms 163556 KB Output is correct
81 Correct 418 ms 294704 KB Output is correct
82 Correct 414 ms 289944 KB Output is correct
83 Correct 397 ms 257732 KB Output is correct
84 Correct 385 ms 254424 KB Output is correct
85 Correct 355 ms 248004 KB Output is correct
86 Correct 347 ms 244888 KB Output is correct
87 Correct 458 ms 285376 KB Output is correct
88 Correct 447 ms 275016 KB Output is correct
89 Correct 412 ms 261628 KB Output is correct
90 Correct 339 ms 243760 KB Output is correct
91 Correct 337 ms 243228 KB Output is correct
92 Correct 339 ms 238048 KB Output is correct