Submission #1048810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048810		Gromp15	Ancient Books (IOI17_books)	C++17	50 / 100	194 ms	195120 KiB

books

#include <bits/stdc++.h>
#include "books.h"
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

template<typename op>
struct sparse_table {
	op x;
	vector<vector<int>> table;
	sparse_table(const vector<int>& a, op t) : table(__lg(sz(a)) + 1, vector<int>(sz(a))), x(t) {
		for (int i = 0; i < sz(a); i++) table[0][i] = a[i];
		for (int i = 1; i <= __lg(sz(a)); i++) {
			for (int j = 0; j < sz(a); j++) {
				if (j + (1 << i) - 1 >= sz(a)) break;
				table[i][j] = x(table[i-1][j], table[i-1][j+(1<<(i-1))]);
			}
		}
	}
	int query(int l, int r) {
		int h = __lg(r-l+1);
		return x(table[h][l], table[h][r-(1<<h)+1]);
	}
};
long long minimum_walk(std::vector<int> p, int s) {
	int n = p.size();
	{
		int l = s, r = s;
		bool F = 0;
		for (int i = 0; i < n; i++) if (i != p[i]) ckmin(l, i), r = i, F = 1;
		if (!F) return 0;
		p = vector<int>(p.begin() + l, p.begin() + r + 1);
		n = r - l + 1;
	}
	vector<int> L(n), R(n);
	long long ans = 0;
	vector<bool> vis(n);
	for (int i = 0; i < n; i++) if (!vis[i]) {
		int right = i;
		int tmp = i;
		vector<int> cur;
		while (!vis[tmp]) {
			cur.emplace_back(tmp);
			ckmax(right, tmp);
			ans += abs(tmp - p[tmp]), vis[tmp] = 1, tmp = p[tmp];
		}
		for (int v : cur) L[v] = i, R[v] = right;
	}
	sparse_table mn(L, [&](int x, int y) { return min(x, y); });
	sparse_table mx(R, [&](int x, int y) { return max(x, y); });
	vector<int> to(n); // [i, s] can reach where
	for (int i = 0; i <= s; i++) {
		to[i] = mn.query(i, s) < i ? to[mn.query(i, s)] : mn.query(i, s);
	}
	vector<int> req(n);
	for (int i = 0; i <= s; i++) req[i] = 1 + (to[i] ? req[to[i] - 1] : 0);

	vector<int> from(n);
	for (int i = n-1; i >= 0; i--) {
		from[i] = mx.query(s, i) > i ? from[mx.query(s, i)] : mx.query(s, i);
	}
	vector<int> req2(n);
	for (int i = n-1; i >= s; i--) req2[i] = 1 + (from[i] + 1 < n ? req2[from[i] + 1] : 0);
	return ans + (req2[s] - 1 + (to[s] ? req[to[s] - 1] : 0)) * 2;
}

Compilation message (stderr)

books.cpp: In instantiation of 'sparse_table<op>::sparse_table(const std::vector<int>&, op) [with op = minimum_walk(std::vector<int>, int)::<lambda(int, int)>]':
books.cpp:51:60:   required from here
books.cpp:12:22: warning: 'sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::table' will be initialized after [-Wreorder]
   12 |  vector<vector<int>> table;
      |                      ^~~~~
books.cpp:11:5: warning:   'minimum_walk(std::vector<int>, int)::<lambda(int, int)> sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::x' [-Wreorder]
   11 |  op x;
      |     ^
books.cpp:13:2: warning:   when initialized here [-Wreorder]
   13 |  sparse_table(const vector<int>& a, op t) : table(__lg(sz(a)) + 1, vector<int>(sz(a))), x(t) {
      |  ^~~~~~~~~~~~
books.cpp: In instantiation of 'sparse_table<op>::sparse_table(const std::vector<int>&, op) [with op = minimum_walk(std::vector<int>, int)::<lambda(int, int)>]':
books.cpp:52:60:   required from here
books.cpp:12:22: warning: 'sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::table' will be initialized after [-Wreorder]
   12 |  vector<vector<int>> table;
      |                      ^~~~~
books.cpp:11:5: warning:   'minimum_walk(std::vector<int>, int)::<lambda(int, int)> sparse_table<minimum_walk(std::vector<int>, int)::<lambda(int, int)> >::x' [-Wreorder]
   11 |  op x;
      |     ^
books.cpp:13:2: warning:   when initialized here [-Wreorder]
   13 |  sparse_table(const vector<int>& a, op t) : table(__lg(sz(a)) + 1, vector<int>(sz(a))), x(t) {
      |  ^~~~~~~~~~~~

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