Submission #415518

#	Time	Username	Problem	Language	Result	Execution time	Memory
415518		SeDunion	Ancient Books (IOI17_books)	C++17	42 / 100	2090 ms	19860 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
void extend(int &l, int &r, vector<int>&C, vector<int>&L, vector<int>&R) {
	int ll = l, rr = r;
  	for (int i = l ; i <= min(r, l + 10) ; ++ i) ll = min(ll, L[C[i]]), rr = max(rr, R[C[i]]);
 	for (int i = max(l, i - 10) ; i <= r ; ++ i) ll = min(ll, L[C[i]]), rr = max(rr, R[C[i]]);
	while (ll != l || rr != r) {
		while (ll < l) {
			--l;
			ll = min(ll, L[C[l]]);
			rr = max(rr, R[C[l]]);
		}
		while (rr > r) {
			++r;
			ll = min(ll, L[C[r]]);
			rr = max(rr, R[C[r]]);
		}
	}
}
 
ll solve(int l, int r, int needl, int needr, vector<int>&C, vector<int>&L, vector<int>&R) {
	extend(l, r, C, L, R);
	if (needl == l && r == needr) return 0ll;
	int l_l = l, r_l = r; ll c_l = 0;
	while (true) {
		if (l_l <= needl) break;
		if (r_l > r) break;
		c_l += 2;
		--l_l;
		extend(l_l, r_l, C, L, R);
	}
	int l_r = l, r_r = r; ll c_r = 0;
	while (true) {
		if (r_r >= needr) break;
		if (l_r < l) break;
		c_r += 2;
		++r_r;
		extend(l_r, r_r, C, L, R);
	}
	assert((l_r < l) == (r_l > r));
	ll res = 0;
	if (l_r < l) res = min(c_l, c_r);
	else res = c_l + c_r;
	int tl = min(l_l, l_r);
	int tr = max(r_l, r_r);
	res += solve(tl, tr, needl, needr, C, L, R);
	//cerr << l << " " << r << " " << needl << " " << needr << " " << res << "\n";
	return res;
}
 
ll minimum_walk(vector<int> p, int s) {
	int n = p.size();
	vector<int>C(n, -1), L(n), R(n);
	int l = s, r = s;
	ll essential = 0;
	for (int i = 0 ; i < n ; ++ i) {
		essential += abs(i - p[i]);
		if (C[i] == -1) {
			L[i] = i;
			R[i] = i;
			int j = i;
			do {
				R[i] = max(R[i], j);
				C[j] = i;
				j = p[j];
			} while (i != j);
		}
		if (p[i] != i) l = min(l, i), r = max(r, i);
	}
	return solve(s, s, l, r, C, L, R) + essential;
}

Compilation message (stderr)

books.cpp: In function 'void extend(int&, int&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
books.cpp:9:25: warning: 'i' is used uninitialized in this function [-Wuninitialized]
    9 |   for (int i = max(l, i - 10) ; i <= r ; ++ i) ll = min(ll, L[C[i]]), rr = max(rr, R[C[i]]);
      |                       ~~^~~~

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