Submission #807761

#	Time	Username	Problem	Language	Result	Execution time	Memory
807761		math_rabbit_1028	Sky Walking (IOI19_walk)	C++14	43 / 100	1474 ms	160780 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 < n; i++) {
		int idx = upper_bound(ylist.begin(), ylist.end(), h[i]) - ylist.begin();
		rem[idx].push_back(i);
	}
	for (int i = 0; i < n; i++) xpset.insert(i);
	for (int i = 0; i < n; i++) xmset.insert(-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.erase(walk[tar].lt);
				xpset.erase(walk[tar].rt);
				xmset.erase(-walk[tar].lt);
				xmset.erase(-walk[tar].rt);
			}
			p++;
		}
		if (walk[i].lt < s && s < walk[i].rt && ylist[walk[i].val] <= h[s]) {
			points.push_back({{*xpset.lower_bound(s), ylist[walk[i].val]}, walk[i].idx});
			points.push_back({{-*xmset.lower_bound(-s), ylist[walk[i].val]}, walk[i].idx});
		}
		if (walk[i].lt < g && g < walk[i].rt && ylist[walk[i].val] <= h[g]) {
			points.push_back({{*xpset.lower_bound(g), ylist[walk[i].val]}, walk[i].idx});
			points.push_back({{-*xmset.lower_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++) rem[i].clear();

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

void print_points() {
	for (int i = 0; i < points.size(); i++) 
		cout << points[i].first.first << " " << points[i].first.second << "\n";
	cout << "\n";
}

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.upper_bound({Y, -num}) == pset.end());
		else if (pset.upper_bound({Y, -num})->first <= h[X]) vertex.push_back({
			{X, pset.upper_bound({Y, -num})->first}, 
			-pset.upper_bound({Y, -num})->second
		});
		if (mset.upper_bound({-Y, -num}) == mset.end());
		else vertex.push_back({
			{X, -mset.upper_bound({-Y, -num})->first}, 
			-mset.upper_bound({-Y, -num})->second
		});
		vertex.push_back({{X, Y}, num});
	}
	for (int i = 0; i < n; i++) add[i].clear();
	for (int i = 0; i < n; i++) rem[i].clear();
	while (pset.size() > 0) pset.erase(pset.begin());
	while (mset.size() > 0) mset.erase(mset.begin());

	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());
}

void print_vertex() {
	for (int i = 0; i < vertex.size(); i++) 
		cout << vertex[i].first.first << " " << vertex[i].first.second << "\n";
	cout << "\n";
}

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.upper_bound({Y, -num}) == pset.end());
		else if (pset.upper_bound({Y, -num})->first <= h[X]) {
			up = {
				{X, pset.upper_bound({Y, -num})->first}, 
				-pset.upper_bound({Y, -num})->second
			};
			adj[now].push_back({
				lower_bound(vertex.begin(), vertex.end(), up) - vertex.begin(),
				up.first.second - Y
			});
			adj[lower_bound(vertex.begin(), vertex.end(), up) - vertex.begin()].push_back({
				now,
				up.first.second - Y
			});
		}
		if (mset.upper_bound({-Y, -num}) == mset.end());
		else {
			dn = {
				{X, -mset.upper_bound({-Y, -num})->first}, 
				-mset.upper_bound({-Y, -num})->second
			};
			adj[now].push_back({
				lower_bound(vertex.begin(), vertex.end(), dn) - vertex.begin(),
				points[i].first.second - dn.first.second
			});
			adj[lower_bound(vertex.begin(), vertex.end(), dn) - vertex.begin()].push_back({
				now,
				points[i].first.second - dn.first.second
			});
		}
	}
	for (int i = 0; i < n; i++) add[i].clear();
	for (int i = 0; i < n; i++) rem[i].clear();
	while (pset.size() > 0) pset.erase(pset.begin());
	while (mset.size() > 0) mset.erase(mset.begin());
}

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 == s) {
			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 == g) {
			adj[i].push_back({ed, vertex[i].first.second});
			adj[ed].push_back({i, vertex[i].first.second});
		}
	}
}

void print_adj() {
	for (int i = 0; i < vertex.size(); i++) {
		for (int j = 0; j < adj[i].size(); j++) {
			cout << vertex[i].first.first << " " << vertex[i].first.second
				 << " " << vertex[adj[i][j].first].first.first 
				 << " " << vertex[adj[i][j].first].first.second
				 << " " << adj[i][j].second << "\n";
		}
	}
}	

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});
			}
		}
	}
}

void print_dis() {
	for (int i = 0; i < vertex.size(); i++) {
		cout << vertex[i].first.first << " " << vertex[i].first.second << " " << dis[i] << "\n";
	}
}

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();
	//print_points();

	get_updn();
	//print_vertex();

	link_updn();
	link_walk();
	link_sted();
	//print_adj();

	dijkstra();
	//print_dis();

	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:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for (int j = 0; j < add[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void print_points()':
walk.cpp:80: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]
   80 |  for (int i = 0; i < points.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void get_updn()':
walk.cpp:92: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]
   92 |  for (int i = 0; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    for (int j = 0; j < add[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    for (int j = 0; j < rem[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void print_vertex()':
walk.cpp:132: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]
  132 |  for (int i = 0; i < vertex.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_updn()':
walk.cpp:143: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]
  143 |  for (int i = 0; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:146:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |    for (int j = 0; j < add[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp:151:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |    for (int j = 0; j < rem[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_walk()':
walk.cpp:200: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]
  200 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:205:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |   for (int j = 1; j < xlist[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'void link_sted()':
walk.cpp:220: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]
  220 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:228: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]
  228 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void print_adj()':
walk.cpp:237: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]
  237 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:238: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]
  238 |   for (int j = 0; j < adj[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void dijkstra()':
walk.cpp:257: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]
  257 |   for (int i = 0; i < adj[now].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'void print_dis()':
walk.cpp:268: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]
  268 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~

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