Submission #301820

#	Time	Username	Problem	Language	Result	Execution time	Memory
301820		QCFium	Sky Walking (IOI19_walk)	C++14	33 / 100	373 ms	30312 KiB

walk

#include <bits/stdc++.h>


struct Way {
	int l;
	int r;
	int y;
};

struct Tower {
	int x;
	int y;
};

long long solve(std::vector<Tower> towers, std::vector<Way> ways, int s, int g) {
	int n = towers.size();
	if (!s && g == n - 1) {
		std::map<int, int> all;
		std::map<int, int64_t> forward, back;
		
		all[0] = 1;
		forward[0] = 0;
		back[0] = 0;
		
		std::vector<int> add[n], remove[n];
		for (auto i : ways) {
			add[i.l].push_back(i.y);
			if (i.r != n - 1) remove[i.r].push_back(i.y);
		}
		remove[0].push_back(0);
		
		for (int i = 0; i < n; i++) {
			for (auto j : add[i]) {
				// std::cerr << "add " << j << std::endl;
				int64_t dist = 1000000000000000000;
				auto itr = forward.upper_bound(j);
				if (itr != forward.begin()) dist = std::min(dist, std::prev(itr)->second + (j - std::prev(itr)->first));
				itr = back.lower_bound(j);
				if (itr != back.end()) dist = std::min(dist, itr->second + (itr->first - j));
				
				all[j]++;
				itr = forward.upper_bound(j);
				if (itr == forward.begin() || (std::prev(itr)->second - std::prev(itr)->first) > dist - j) {
					forward[j] = dist;
					while (itr != forward.end() && itr->second - itr->first > dist - j) itr = forward.erase(itr);
				}
				itr = back.lower_bound(j);
				if (itr == back.end() || itr->first + itr->second > dist + j) {
					back[j] = dist;
					while (itr != back.begin() && std::prev(itr)->first + std::prev(itr)->second > dist + j) back.erase(std::prev(itr));
				}
			}
			for (auto j : remove[i]) {
				// std::cerr << "remove " << j << std::endl;
				if (all[j] == 1) {
					if (forward.count(j)) {
						auto itr = all.upper_bound(j);
						if (itr != all.end() && !forward.count(itr->first)) forward[itr->first] = forward[j] + (itr->first - j);
						forward.erase(j);
					}
					if (back.count(j)) {
						auto itr = all.lower_bound(j);
						if (itr != all.begin() && !back.count(std::prev(itr)->first))
							back[std::prev(itr)->first] = back[j] + (j - std::prev(itr)->first);
						back.erase(j);
					}
					
					all.erase(j);
				} else all[j]--;
			}
			/*
			std::cerr << "all : ";
			for (auto i : all) std::cerr << "{" << i.first << "," << i.second << "}  ";
			std::cerr << std::endl;
			std::cerr << "forward : ";
			for (auto i : forward) std::cerr << "{" << i.first << "," << i.second << "}  ";
			std::cerr << std::endl;
			std::cerr << "back : ";
			for (auto i : back) std::cerr << "{" << i.first << "," << i.second << "}  ";
			std::cerr << std::endl;*/
		}
		if (!back.size()) return -1;
		int64_t res = back.begin()->second + back.begin()->first;
		if (res > 500000000000000000) return -1;
		return res + (towers.back().x - towers.front().x);
	}
	assert(0);
	return -1;
}

long long min_distance(std::vector<int> a, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	std::vector<Tower> towers;
	for (int i = 0; i < (int) a.size(); i++) towers.push_back({a[i], h[i]});
	std::vector<Way> ways;
	for (int i = 0; i < (int) l.size(); i++) ways.push_back({l[i], r[i], y[i]});
	return solve(towers, ways, s, g);
}

/*
int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
}
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43