Submission #1175495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175495		xnqs	Fire (BOI24_fire)	C++20	0 / 100	20 ms	2640 KiB

Main

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>

int x, max_coord;
std::vector<std::pair<int,int>> arr;
std::vector<std::vector<int>> next;
std::map<int,int> norm_r;

void read_data() {
	std::cin >> x >> max_coord;

	bool has_start = 0, has_finish = 0;
	for (int i = 0, a, b; i < x; i++) {
		std::cin >> a >> b;
		if (a <= b) {
			if (a == 0) {
				has_start = 1;
			}
			if (b == max_coord-1) {
				has_finish = 1;
			}
		}
		else {
			has_start = 1;
			has_finish = 1;
		}

		a = std::max(0, a-1);
		arr.emplace_back(a,b);
	}

	if (!has_start || !has_finish) {
		std::cout << "-1\n";
		exit(0);
	}
}

void normalize_data() {
	std::map<int,int> map;
	for (int i = 0; i < x; i++) {
		if (arr[i].first+1 <= arr[i].second) {
			map[arr[i].first] = 0;
			map[arr[i].second] = 0;
		}
		else {
			map[0] = 0;
			map[max_coord-1] = 0;
			map[arr[i].first] = 0;
			map[arr[i].second] = 0;
		}
	}

	max_coord = 0;
	for (auto& i : map) {
		i.second = max_coord++;
		norm_r[max_coord-1] = i.first;
		//std::cout << i.first << " " << i.second << "\n";
	}

	for (int i = 0; i < x; i++) {
		arr[i].first = map[arr[i].first];
		arr[i].second = map[arr[i].second];
		//std::cout << arr[i].first << " " << arr[i].second << "\n";
	}
}

void build_jump_table() {
	next.assign(32-__builtin_clz(max_coord), std::vector<int>(max_coord, 0));
	std::vector<int> tmp(max_coord, 0);
	for (int i = 0; i < x; i++) {
		if (arr[i].first+1 <= arr[i].second) {
			tmp[arr[i].first] = std::max(tmp[arr[i].first], arr[i].second);
		}
		else {
			tmp[0] = std::max(tmp[0], arr[i].second);
			tmp[arr[i].first] = std::max(tmp[arr[i].first], max_coord-1);
		}
	}

	int pfx_max = 0;
	for (int i = 0; i < max_coord; i++) {
		pfx_max = std::max(pfx_max, tmp[i]);
		next[0][i] = std::max(pfx_max, i);
		//std::cout << tmp[i] << " ";
		//std::cout << next[0][i] << " ";
	}
	//std::cout << "\n";

	for (int l = 1; l < next.size(); l++) {
		for (int i = 0; i < max_coord; i++) {
			next[l][i] = next[l-1][next[l-1][i]];
		}
	}
}

int try_solve(int st, int fi) {
	int ret = 0;
	int p = st;
	for (int step = next.size()-1; step >= 0; step--) {
		if (next[step][p] < fi) {
			ret += (1<<step);
			p = next[step][p];
		}
	}

	return ((next[0][p]>=fi) ? ret + (p < fi) : 0x3f3f3f3f);
}

void solve() {
	int ret = 0x3f3f3f3f;
	ret = std::min(ret, try_solve(0, max_coord-1));
	for (int i = 0; i < x; i++) {
		if (arr[i].first+1 > arr[i].second) {
			ret = std::min(ret, 1 + try_solve(arr[i].second, arr[i].first - (norm_r[arr[i].first-1]+1==norm_r[arr[i].first])));
		}
	}

	std::cout << ((ret!=0x3f3f3f3f) ? ret : -1) << "\n";
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	read_data();
	normalize_data();
	build_jump_table();
	solve();
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 17
• Subtask 3: 0 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26