Submission #425148

#	Time	Username	Problem	Language	Result	Execution time	Memory
425148		donentseto	Sky Walking (IOI19_walk)	C++14	24 / 100	1125 ms	150384 KiB

walk

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;
int n, m, nodes;
struct building{
	int x, h;
	bool operator < (building oth) const{
		return x < oth.x;
	}
};
bool comp (building a, building b){
	return a.h < b.h;
}
struct skywalk{
	int l, r, y;
	bool operator < (skywalk oth) const{
		return y < oth.y;
	}
};
vector <building> b;
set <building> s;
vector <skywalk> w;
vector <pair <int, int> > intersect [maxn];
vector <pair <int, int> > adj [maxn * 10];
bool used [maxn * 10];

long long dejkstra (int a, int A){

	priority_queue <pair <long long, int> > pq;
	pq.push ({0, a});
	while (!pq.empty ()){
		auto p = pq.top ();
		pq.pop ();
		if (used [p.second]) continue;
		if (p.second == A) return -p.first;
		used [p.second] = 1;
		for (auto e : adj [p.second]){
			if (used [e.first]) continue;
			pq.push ({p.first - e.second, e.first});
		}
	}

	return -1;

}

long long min_distance (vector <int> x, vector <int> h, vector <int> l, vector <int> r, vector <int> y, int start, int end){

	n = x.size ();
	m = l.size ();
	for (int i = 0; i < n; i ++){
		b.push_back ({i, h [i]});
	}
	for (int i = 0; i < m; i ++){
		w.push_back ({l [i], r [i], y [i]});
	}
	sort (b.begin (), b.end (), comp);
	sort (w.begin (), w.end ());

	int idx = n - 1;
	for (int i = m - 1; i >= 0; i --){
		while (idx >= 0 && b [idx].h >= w [i].y){
			s.insert (b [idx]);
			idx --;
		}
		building b = {w [i].l, 0};
		auto it = s.lower_bound (b);
		vector <int> v;
		while ((*it).x != w [i].r){
			v.push_back ((*it).x);
			++it;
		}
		v.push_back (w [i].r);
		int sz = v.size ();
		intersect [v [0]].push_back ({w [i].y, nodes ++});
		for (int j = 1; j < sz; j ++){
			adj [nodes - 1].push_back ({nodes, x [v [j]] - x [v [j - 1]]});
			adj [nodes].push_back ({nodes - 1, x [v [j]] - x [v [j - 1]]});
			intersect [v [j]].push_back ({w [i].y, nodes ++});
		}
	}
	intersect [start].push_back ({0, nodes ++});
	intersect [end].push_back ({0, nodes ++});
	for (int i = 0; i < n; i ++){
		int sz = intersect [i].size ();
		for (int j = 1; j < sz; j ++){
			adj [intersect [i][j].second].push_back ({intersect [i][j - 1].second, intersect [i][j - 1].first - intersect [i][j].first});
			adj [intersect [i][j - 1].second].push_back ({intersect [i][j].second, intersect [i][j - 1].first - intersect [i][j].first});
		}
	}

	return dejkstra (nodes - 2, nodes - 1);

}
/*
int main (){

	cout << min_distance({0, 3, 5, 7, 10, 12, 14},
			{8, 7, 9, 7, 6, 6, 9},
			{0, 0, 0, 2, 2, 3, 4},
			{1, 2, 6, 3, 6, 4, 6},
			{1, 6, 8, 1, 7, 2, 5},
			1, 5) << '\n';

}*/

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