Submission #301887

#	Time	Username	Problem	Language	Result	Execution time	Memory
301887		QCFium	Sky Walking (IOI19_walk)	C++14	57 / 100	4058 ms	724792 KiB

walk

#include <bits/stdc++.h>


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

struct Tower {
	int x;
	int y;
};

struct SegTree {
	int n;
	std::vector<std::vector<std::pair<int, int> > > data;
	SegTree (std::vector<int> a) {
		for (n = 1; n < (int) a.size(); n <<= 1);
		data.resize(n << 1);
		for (int i = 0; i < (int) a.size(); i++) data[i + n] = { {a[i], i} };
		for (int i = n; --i; ) {
			data[i].resize(data[i << 1].size() + data[i << 1 | 1].size());
			std::merge(data[i << 1].begin(), data[i << 1].end(), data[i << 1 | 1].begin(), data[i << 1 | 1].end(), data[i].begin());
		}
	}
	std::vector<int> greater_list(int l, int r, int x) {
		std::vector<int> res;
		auto process = [&] (std::vector<std::pair<int, int> > data) {
			for (int i = data.size(); i--; ) {
				if (data[i].first < x) break;
				res.push_back(data[i].second);
			}
		};
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (r & 1) process(data[--r]);
			if (l & 1) process(data[l++]);
		}
		return res;
	}
};

template<typename T> using pqueue_inv = std::priority_queue<T, std::vector<T>, std::greater<T> >;

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]) {
				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]) {
				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]--;
			}
		}
		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);
	}
	
	if (towers.size() <= 50 && ways.size() <= 50) {
		std::vector<int> ys{0};
		for (auto i : ways) ys.push_back(i.y);
		std::sort(ys.begin(), ys.end());
		ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
		auto compress = [&] (int i) { return std::lower_bound(ys.begin(), ys.end(), i) - ys.begin(); };
		
		int h = ys.size();
		
		std::vector<std::pair<int, int> > hen[n * h];
		auto add = [&] (int i, int j, int c) {
			hen[i].push_back({j, c});
			hen[j].push_back({i, c});
		};
		for (int i = 0; i < n; i++) for (int j = 1; j < h; j++) if (ys[j] <= towers[i].y) add(i * h + j, i * h + j - 1, ys[j] - ys[j - 1]);
		for (auto i : ways) {
			int cur_h = compress(i.y);
			// std::cerr << i.l << "," << i.r << " " << i.y << "->" << cur_h << std::endl;
			int last = i.l;
			for (int j = i.l; ++j <= i.r; ) {
				// std::cerr << "  " << towers[j].y << " " << i.y << std::endl;
				if (towers[j].y >= i.y) {
					// std::cerr << "   at " << j << std::endl;
					add(last * h + cur_h, j * h + cur_h, towers[j].x - towers[last].x);
					last = j;
				}
			}
		}
		
		std::vector<int64_t> dist(n * h, 1000000000000000000);
		pqueue_inv<std::pair<int64_t, int> > que;
		que.push({dist[s * h] = 0, s * h});
		while (que.size()) {
			auto i = que.top();
			que.pop();
			// std::cerr << i.second << " " << i.first << std::endl;
			if (i.first != dist[i.second]) continue;
			for (auto j : hen[i.second]) if (dist[j.first] > i.first + j.second)
				que.push({dist[j.first] = i.first + j.second, j.first});
		}
		int64_t res = dist[g * h];
		if (res > 500000000000000000) return -1;
		return res;
	} else {
		std::vector<int> heights;
		for (auto i : towers) heights.push_back(i.y);
		SegTree tree(heights);
		
		std::map<int, int> ids[n];
		std::vector<int> list[ways.size()];
		for (int i = 0; i < (int) ways.size(); i++) {
			list[i] = tree.greater_list(ways[i].l, ways[i].r + 1, ways[i].y);
			std::sort(list[i].begin(), list[i].end());
			for (auto j : list[i]) ids[j][ways[i].y];
		}
		ids[s][0];
		ids[g][0];
		
		struct Hen {
			int a;
			int b;
			int c;
		};
		std::vector<Hen> hens;
		
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			int last = -1;
			for (auto &j : ids[i]) {
				if (last != -1) hens.push_back({cnt - 1, cnt, j.first - last});
				last = j.first;
				j.second = cnt++;
			}
		}
		for (int i = 0; i < (int) ways.size(); i++) {
			int last_x = -1;
			int last_id = -1;
			for (auto j : list[i]) {
				int id = ids[j][ways[i].y];
				if (last_x != -1) hens.push_back({last_id, id, towers[j].x - last_x});
				last_x = towers[j].x;
				last_id = id;
			}
		}
		
		std::vector<std::pair<int, int> > hen[cnt];
		for (auto i : hens) {
			hen[i.a].push_back({i.b, i.c});
			hen[i.b].push_back({i.a, i.c});
		}
		
		std::vector<int64_t> dist(cnt, 1000000000000000000);
		pqueue_inv<std::pair<int64_t, int> > que;
		que.push({dist[ids[s][0]] = 0, ids[s][0]});
		while (que.size()) {
			auto i = que.top();
			que.pop();
			// std::cerr << i.second << " " << i.first << std::endl;
			if (i.first != dist[i.second]) continue;
			for (auto j : hen[i.second]) if (dist[j.first] > i.first + j.second)
				que.push({dist[j.first] = i.first + j.second, j.first});
		}
		int64_t res = dist[ids[g][0]];
		if (res > 500000000000000000) return -1;
		return res;
	}
	
	
	
	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: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43