Submission #390668

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
390668	2021-04-16T13:26:52 Z	Keshi	Ancient Books (IOI17_books)	C++17	70 / 100	2000 ms	86816 KB

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 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];
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[maxn << 2];

void bld(ll id, ll s, ll e){
	if(e - s == 1){
		seg[id] = b[s];
		return;
	}
	ll mid = (s + e) >> 1;
	bld(lc, s, mid);
	bld(rc, mid, e);
	seg[id] = max(seg[lc], seg[rc]);
}
ll get(ll id, ll s, ll e, ll l, ll r){
	if(r <= s || e <= l) return 0;
	if(l <= s && e <= r) return seg[id];
	ll mid = (s + e) >> 1;
	return max(get(lc, s, mid, l, r), get(rc, mid, e, l, r));
}

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){
	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(1, 0, 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(1, 0, n, 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.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23884 KB	Output is correct
2	Correct	15 ms	23884 KB	Output is correct
3	Correct	16 ms	23800 KB	Output is correct
4	Correct	16 ms	23884 KB	Output is correct
5	Correct	17 ms	23804 KB	Output is correct
6	Correct	15 ms	23756 KB	Output is correct
7	Correct	15 ms	23756 KB	Output is correct
8	Correct	15 ms	23852 KB	Output is correct
9	Correct	17 ms	23756 KB	Output is correct
10	Correct	15 ms	23756 KB	Output is correct
11	Correct	15 ms	23760 KB	Output is correct
12	Correct	15 ms	23756 KB	Output is correct
13	Correct	15 ms	23884 KB	Output is correct
14	Correct	15 ms	23756 KB	Output is correct
15	Correct	15 ms	23880 KB	Output is correct
16	Correct	16 ms	23756 KB	Output is correct
17	Correct	16 ms	23832 KB	Output is correct
18	Correct	15 ms	23756 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23884 KB	Output is correct
2	Correct	15 ms	23884 KB	Output is correct
3	Correct	16 ms	23800 KB	Output is correct
4	Correct	16 ms	23884 KB	Output is correct
5	Correct	17 ms	23804 KB	Output is correct
6	Correct	15 ms	23756 KB	Output is correct
7	Correct	15 ms	23756 KB	Output is correct
8	Correct	15 ms	23852 KB	Output is correct
9	Correct	17 ms	23756 KB	Output is correct
10	Correct	15 ms	23756 KB	Output is correct
11	Correct	15 ms	23760 KB	Output is correct
12	Correct	15 ms	23756 KB	Output is correct
13	Correct	15 ms	23884 KB	Output is correct
14	Correct	15 ms	23756 KB	Output is correct
15	Correct	15 ms	23880 KB	Output is correct
16	Correct	16 ms	23756 KB	Output is correct
17	Correct	16 ms	23832 KB	Output is correct
18	Correct	15 ms	23756 KB	Output is correct
19	Correct	16 ms	23884 KB	Output is correct
20	Correct	16 ms	24000 KB	Output is correct
21	Correct	16 ms	23812 KB	Output is correct
22	Correct	16 ms	23884 KB	Output is correct
23	Correct	16 ms	23896 KB	Output is correct
24	Correct	16 ms	23840 KB	Output is correct
25	Correct	16 ms	23828 KB	Output is correct
26	Correct	16 ms	23884 KB	Output is correct
27	Correct	15 ms	23884 KB	Output is correct
28	Correct	19 ms	23868 KB	Output is correct
29	Correct	16 ms	23884 KB	Output is correct

Subtask #3
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23884 KB	Output is correct
2	Correct	15 ms	23884 KB	Output is correct
3	Correct	16 ms	23800 KB	Output is correct
4	Correct	16 ms	23884 KB	Output is correct
5	Correct	17 ms	23804 KB	Output is correct
6	Correct	15 ms	23756 KB	Output is correct
7	Correct	15 ms	23756 KB	Output is correct
8	Correct	15 ms	23852 KB	Output is correct
9	Correct	17 ms	23756 KB	Output is correct
10	Correct	15 ms	23756 KB	Output is correct
11	Correct	15 ms	23760 KB	Output is correct
12	Correct	15 ms	23756 KB	Output is correct
13	Correct	15 ms	23884 KB	Output is correct
14	Correct	15 ms	23756 KB	Output is correct
15	Correct	15 ms	23880 KB	Output is correct
16	Correct	16 ms	23756 KB	Output is correct
17	Correct	16 ms	23832 KB	Output is correct
18	Correct	15 ms	23756 KB	Output is correct
19	Correct	16 ms	23884 KB	Output is correct
20	Correct	16 ms	24000 KB	Output is correct
21	Correct	16 ms	23812 KB	Output is correct
22	Correct	16 ms	23884 KB	Output is correct
23	Correct	16 ms	23896 KB	Output is correct
24	Correct	16 ms	23840 KB	Output is correct
25	Correct	16 ms	23828 KB	Output is correct
26	Correct	16 ms	23884 KB	Output is correct
27	Correct	15 ms	23884 KB	Output is correct
28	Correct	19 ms	23868 KB	Output is correct
29	Correct	16 ms	23884 KB	Output is correct
30	Correct	204 ms	40892 KB	Output is correct
31	Correct	194 ms	41752 KB	Output is correct
32	Correct	141 ms	32452 KB	Output is correct
33	Correct	427 ms	78328 KB	Output is correct
34	Correct	418 ms	78368 KB	Output is correct
35	Correct	379 ms	71200 KB	Output is correct
36	Correct	284 ms	60724 KB	Output is correct
37	Correct	199 ms	51028 KB	Output is correct
38	Correct	187 ms	48708 KB	Output is correct
39	Correct	184 ms	48196 KB	Output is correct
40	Correct	185 ms	43844 KB	Output is correct
41	Correct	184 ms	41880 KB	Output is correct
42	Correct	184 ms	42272 KB	Output is correct
43	Correct	477 ms	82572 KB	Output is correct

Subtask #4
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23888 KB	Output is correct
2	Correct	16 ms	23884 KB	Output is correct
3	Correct	16 ms	23884 KB	Output is correct
4	Correct	16 ms	23916 KB	Output is correct
5	Correct	16 ms	23908 KB	Output is correct
6	Correct	16 ms	23884 KB	Output is correct
7	Correct	16 ms	23888 KB	Output is correct
8	Correct	16 ms	23892 KB	Output is correct
9	Correct	16 ms	23844 KB	Output is correct
10	Correct	16 ms	23720 KB	Output is correct
11	Correct	16 ms	23924 KB	Output is correct
12	Correct	16 ms	23884 KB	Output is correct
13	Correct	16 ms	23832 KB	Output is correct
14	Correct	15 ms	23884 KB	Output is correct
15	Correct	15 ms	23808 KB	Output is correct
16	Correct	16 ms	23884 KB	Output is correct
17	Correct	16 ms	23884 KB	Output is correct
18	Correct	16 ms	23884 KB	Output is correct
19	Correct	16 ms	23884 KB	Output is correct
20	Correct	15 ms	23884 KB	Output is correct

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23884 KB	Output is correct
2	Correct	15 ms	23884 KB	Output is correct
3	Correct	16 ms	23800 KB	Output is correct
4	Correct	16 ms	23884 KB	Output is correct
5	Correct	17 ms	23804 KB	Output is correct
6	Correct	15 ms	23756 KB	Output is correct
7	Correct	15 ms	23756 KB	Output is correct
8	Correct	15 ms	23852 KB	Output is correct
9	Correct	17 ms	23756 KB	Output is correct
10	Correct	15 ms	23756 KB	Output is correct
11	Correct	15 ms	23760 KB	Output is correct
12	Correct	15 ms	23756 KB	Output is correct
13	Correct	15 ms	23884 KB	Output is correct
14	Correct	15 ms	23756 KB	Output is correct
15	Correct	15 ms	23880 KB	Output is correct
16	Correct	16 ms	23756 KB	Output is correct
17	Correct	16 ms	23832 KB	Output is correct
18	Correct	15 ms	23756 KB	Output is correct
19	Correct	16 ms	23884 KB	Output is correct
20	Correct	16 ms	24000 KB	Output is correct
21	Correct	16 ms	23812 KB	Output is correct
22	Correct	16 ms	23884 KB	Output is correct
23	Correct	16 ms	23896 KB	Output is correct
24	Correct	16 ms	23840 KB	Output is correct
25	Correct	16 ms	23828 KB	Output is correct
26	Correct	16 ms	23884 KB	Output is correct
27	Correct	15 ms	23884 KB	Output is correct
28	Correct	19 ms	23868 KB	Output is correct
29	Correct	16 ms	23884 KB	Output is correct
30	Correct	204 ms	40892 KB	Output is correct
31	Correct	194 ms	41752 KB	Output is correct
32	Correct	141 ms	32452 KB	Output is correct
33	Correct	427 ms	78328 KB	Output is correct
34	Correct	418 ms	78368 KB	Output is correct
35	Correct	379 ms	71200 KB	Output is correct
36	Correct	284 ms	60724 KB	Output is correct
37	Correct	199 ms	51028 KB	Output is correct
38	Correct	187 ms	48708 KB	Output is correct
39	Correct	184 ms	48196 KB	Output is correct
40	Correct	185 ms	43844 KB	Output is correct
41	Correct	184 ms	41880 KB	Output is correct
42	Correct	184 ms	42272 KB	Output is correct
43	Correct	477 ms	82572 KB	Output is correct
44	Correct	16 ms	23888 KB	Output is correct
45	Correct	16 ms	23884 KB	Output is correct
46	Correct	16 ms	23884 KB	Output is correct
47	Correct	16 ms	23916 KB	Output is correct
48	Correct	16 ms	23908 KB	Output is correct
49	Correct	16 ms	23884 KB	Output is correct
50	Correct	16 ms	23888 KB	Output is correct
51	Correct	16 ms	23892 KB	Output is correct
52	Correct	16 ms	23844 KB	Output is correct
53	Correct	16 ms	23720 KB	Output is correct
54	Correct	16 ms	23924 KB	Output is correct
55	Correct	16 ms	23884 KB	Output is correct
56	Correct	16 ms	23832 KB	Output is correct
57	Correct	15 ms	23884 KB	Output is correct
58	Correct	15 ms	23808 KB	Output is correct
59	Correct	16 ms	23884 KB	Output is correct
60	Correct	16 ms	23884 KB	Output is correct
61	Correct	16 ms	23884 KB	Output is correct
62	Correct	16 ms	23884 KB	Output is correct
63	Correct	15 ms	23884 KB	Output is correct
64	Correct	439 ms	83980 KB	Output is correct
65	Execution timed out	2028 ms	86816 KB	Time limit exceeded
66	Halted	0 ms	0 KB	-

Submission #390668

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 28.0 / 28.0

Subtask #4 20.0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
28.0 / 28.0

Subtask #4
20.0 / 20.0

Subtask #5
0 / 30.0