Submission #807228

#	Time	Username	Problem	Language	Result	Execution time	Memory
807228		math_rabbit_1028	Sky Walking (IOI19_walk)	C++14	0 / 100	712 ms	140256 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, s, g;
vector<int> x, h, l, r, y;

struct sky {
	int lt, rt, val, idx;
} walk[101010];
bool compare(sky a, sky b) {
	if (a.rt == b.rt) return a.lt > b.lt;
	return a.rt < b.rt;
}
void sort_end() {
	for (int i = 0; i < m; i++) walk[i] = {l[i], r[i], y[i]};
	sort(walk, walk + m, compare);
	for (int i = 0; i < m; i++) {
		l[i] = walk[i].lt;
		r[i] = walk[i].rt;
		y[i] = walk[i].val;
	}
}

set<int> xpset, xmset;
vector< pair< pair<int, int>, int > > points;
vector<int> ylist;
vector<int> add[101010], rem[101010];
bool compval(sky a, sky b) {
	return a.val < b.val;
}
void get_points() {
	for (int i = 0; i < m; i++) ylist.push_back(walk[i].val);
	sort(ylist.begin(), ylist.end());
	ylist.erase(unique(ylist.begin(), ylist.end()), ylist.end());
	
	for (int i = 0; i < m; i++) walk[i].idx = i;
	sort(walk, walk + m, compval);
	for (int i = 0; i < m; i++) 
		walk[i].val = lower_bound(ylist.begin(), ylist.end(), walk[i].val) - ylist.begin();

	for (int i = 0; i < m; i++) add[walk[i].val].push_back(i);

	int p = 0;
	for (int i = 0; i < m; i++) {
		while (p <= walk[i].val) {
			for (int j = 0; j < add[p].size(); j++) {
				int tar = add[p][j];
				xpset.insert(tar);
				xmset.insert(-tar);
			}
			p++;
		}
		if (walk[i].lt < s && s < walk[i].rt) {
			points.push_back({{*xpset.upper_bound(s), ylist[walk[i].val]}, walk[i].idx});
			points.push_back({{-*xmset.upper_bound(-s), ylist[walk[i].val]}, walk[i].idx});
		}
		if (walk[i].lt < g && g < walk[i].rt) {
			points.push_back({{*xpset.upper_bound(g), ylist[walk[i].val]}, walk[i].idx});
			points.push_back({{-*xmset.upper_bound(-g), ylist[walk[i].val]}, walk[i].idx});
		}
		points.push_back({{walk[i].lt, ylist[walk[i].val]}, walk[i].idx});
		points.push_back({{walk[i].rt, ylist[walk[i].val]}, walk[i].idx});
	}
	for (int i = 0; i < m; i++) add[i].clear();

	sort(points.begin(), points.end());
	points.erase(unique(points.begin(), points.end()), points.end());
}

set< pair<int, int> > pset, mset;
vector< pair< pair<int, int>, int > > vertex;
void get_updn() {
	for (int i = 0; i < m; i++) add[l[i]].push_back(i);
	for (int i = 0; i < m; i++) rem[r[i] + 1].push_back(i);

	int p = 0;
	for (int i = 0; i < points.size(); i++) {
		int X = points[i].first.first, Y = points[i].first.second, num = points[i].second;
		while (p <= X) {
			for (int j = 0; j < add[p].size(); j++) {
				int tar = add[p][j];
				pset.insert({y[tar], tar});
				mset.insert({-y[tar], tar});
			}
			for (int j = 0; j < rem[p].size(); j++) {
				int tar = rem[p][j];
				pset.erase({y[tar], tar});
				mset.erase({-y[tar], tar});
			}
			p++;
		}

		if (pset.lower_bound({Y, num + 1}) == pset.end());
		else vertex.push_back({
			{X, pset.lower_bound({Y, num + 1})->first}, 
			pset.lower_bound({Y, num + 1})->second
		});
		if (mset.lower_bound({-Y, num + 1}) == mset.end());
		else vertex.push_back({
			{X, -mset.lower_bound({-Y, num + 1})->first}, 
			mset.lower_bound({-Y, num + 1})->second
		});
		vertex.push_back({{X, Y}, num});
	}
	for (int i = 0; i < m; i++) add[i].clear();
	for (int i = 0; i < m; i++) rem[i].clear();

	vertex.push_back({{s, 0}, -1});
	vertex.push_back({{g, 0}, -1});
	sort(vertex.begin(), vertex.end());
	vertex.erase(unique(vertex.begin(), vertex.end()), vertex.end());
}

vector< pair<int, ll> > adj[2020202];
void link_updn() {
	for (int i = 0; i < m; i++) add[l[i]].push_back(i);
	for (int i = 0; i < m; i++) rem[r[i] + 1].push_back(i);

	int p = 0;
	for (int i = 0; i < points.size(); i++) {
		int X = points[i].first.first, Y = points[i].first.second, num = points[i].second;
		while (p <= X) {
			for (int j = 0; j < add[p].size(); j++) {
				int tar = add[p][j];
				pset.insert({y[tar], tar});
				mset.insert({-y[tar], tar});
			}
			for (int j = 0; j < rem[p].size(); j++) {
				int tar = rem[p][j];
				pset.erase({y[tar], tar});
				mset.erase({-y[tar], tar});
			}
			p++;
		}

		int now = lower_bound(vertex.begin(), vertex.end(), points[i]) - vertex.begin();
		pair< pair<int, int>, int > up, dn;
		if (pset.lower_bound({Y, num + 1}) == pset.end());
		else {
			up = {
				{X, pset.lower_bound({Y, num + 1})->first}, 
				pset.lower_bound({Y, num + 1})->second
			};
			adj[now].push_back({
				lower_bound(vertex.begin(), vertex.end(), up) - vertex.begin(),
				pset.lower_bound({Y, num + 1})->first - points[i].first.second
			});
			adj[lower_bound(vertex.begin(), vertex.end(), up) - vertex.begin()].push_back({
				now,
				pset.lower_bound({Y, num + 1})->first - points[i].first.second
			});
		}
		if (mset.lower_bound({-Y, num + 1}) == mset.end());
		else {
			dn = {
				{X, -mset.lower_bound({-Y, num + 1})->first}, 
				mset.lower_bound({-Y, num + 1})->second
			};
			adj[now].push_back({
				lower_bound(vertex.begin(), vertex.end(), dn) - vertex.begin(),
				points[i].first.second + mset.lower_bound({-Y, num + 1})->first
			});
			adj[lower_bound(vertex.begin(), vertex.end(), dn) - vertex.begin()].push_back({
				now,
				points[i].first.second + mset.lower_bound({-Y, num + 1})->first
			});
		}
	}
	for (int i = 0; i < m; i++) add[i].clear();
	for (int i = 0; i < m; i++) rem[i].clear();
}

vector<int> xlist[101010];
void link_walk() {
	for (int i = 0; i < vertex.size(); i++) {
		if (vertex[i].second >= 0) xlist[vertex[i].second].push_back(vertex[i].first.first);
	}
	for (int i = 0; i < m; i++) sort(xlist[i].begin(), xlist[i].end());
	for (int i = 0; i < m; i++) {
		for (int j = 1; j < xlist[i].size(); j++) {
			int lt = lower_bound(vertex.begin(), vertex.end(), make_pair(
				make_pair(xlist[i][j - 1], y[i]), i
			)) - vertex.begin();
			int rt = lower_bound(vertex.begin(), vertex.end(), make_pair(
				make_pair(xlist[i][j], y[i]), i
			)) - vertex.begin();
			adj[lt].push_back({rt, x[xlist[i][j]] - x[xlist[i][j - 1]]});
			adj[rt].push_back({lt, x[xlist[i][j]] - x[xlist[i][j - 1]]});
		}
	}
}

void link_sted() {
	int st = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(s, 0), -1)) - vertex.begin();
	for (int i = 0; i < vertex.size(); i++) {
		if (vertex[i].first.first == 0) {
			adj[i].push_back({st, vertex[i].first.second});
			adj[st].push_back({i, vertex[i].first.second});
		}
	}
	
	int ed = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(g, 0), -1)) - vertex.begin();
	for (int i = 0; i < vertex.size(); i++) {
		if (vertex[i].first.first == n - 1) {
			adj[i].push_back({ed, vertex[i].first.second});
			adj[ed].push_back({i, vertex[i].first.second});
		}
	}
}	

ll dis[2020202];
priority_queue< pair<ll, int> > pq;
void dijkstra() {
	for (int i = 0; i <= 2000000; i++) dis[i] = 1e18;
	int st = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(s, 0), -1)) - vertex.begin();
	dis[st] = 0;
	pq.push({-dis[st], st});
	while (!pq.empty()) {
		int now = pq.top().second; ll nowdis = -pq.top().first;
		pq.pop();
		for (int i = 0; i < adj[now].size(); i++) {
			int next = adj[now][i].first;
			if (dis[next] > nowdis + adj[now][i].second) {
				dis[next] = nowdis + adj[now][i].second;
				pq.push({-dis[next], next});
			}
		}
	}
}

ll min_distance(std::vector<int> X, std::vector<int> H, std::vector<int> L, std::vector<int> R, std::vector<int> Y, int S, int G) {
	x = X; h = H; l = L; r = R; y = Y; s = S; g = G;
	n = x.size();
	m = l.size();
	sort_end();

	get_points();
  
	get_updn();

	link_updn();
	link_walk();
	link_sted();

	dijkstra();

	int ed = lower_bound(vertex.begin(), vertex.end(), make_pair(make_pair(g, 0), -1)) - vertex.begin();
	ll ans = dis[ed];
	if (ans >= 1e18) return -1;
	return ans;
}

Compilation message (stderr)

walk.cpp: In function 'void get_points()':
walk.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for (int j = 0; j < add[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void get_updn()':
walk.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    for (int j = 0; j < add[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    for (int j = 0; j < rem[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_updn()':
walk.cpp:122:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |  for (int i = 0; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |    for (int j = 0; j < add[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |    for (int j = 0; j < rem[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_walk()':
walk.cpp:177:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:182:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |   for (int j = 1; j < xlist[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'void link_sted()':
walk.cpp:197:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:205:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void dijkstra()':
walk.cpp:223:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |   for (int i = 0; i < adj[now].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~

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