oj.uz

Submission #807761

# Submission time Handle Problem Language Result Execution time Memory
807761 2023-08-05T00:53:43 Z math_rabbit_1028 Sky Walking (IOI19_walk) C++14
43 / 100
 1474 ms 160780 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70512 KB Output is correct
2 Correct 34 ms 70416 KB Output is correct
3 Correct 29 ms 70488 KB Output is correct
4 Correct 33 ms 70476 KB Output is correct
5 Correct 30 ms 70556 KB Output is correct
6 Correct 30 ms 70544 KB Output is correct
7 Correct 30 ms 70524 KB Output is correct
8 Correct 29 ms 70484 KB Output is correct
9 Correct 30 ms 70484 KB Output is correct
10 Correct 33 ms 70484 KB Output is correct
11 Correct 31 ms 70476 KB Output is correct
12 Correct 31 ms 70484 KB Output is correct
13 Correct 29 ms 70484 KB Output is correct
14 Correct 29 ms 70532 KB Output is correct
15 Correct 30 ms 70432 KB Output is correct
16 Correct 29 ms 70488 KB Output is correct
17 Correct 29 ms 70480 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 70472 KB Output is correct
2 Correct 28 ms 70484 KB Output is correct
3 Correct 648 ms 128284 KB Output is correct
4 Correct 601 ms 140504 KB Output is correct
5 Correct 436 ms 126344 KB Output is correct
6 Correct 434 ms 123660 KB Output is correct
7 Correct 424 ms 126612 KB Output is correct
8 Correct 669 ms 131212 KB Output is correct
9 Correct 511 ms 134928 KB Output is correct
10 Incorrect 579 ms 141976 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 94440 KB Output is correct
2 Correct 959 ms 141172 KB Output is correct
3 Correct 1022 ms 144604 KB Output is correct
4 Correct 1069 ms 157632 KB Output is correct
5 Correct 1381 ms 160364 KB Output is correct
6 Correct 1362 ms 157248 KB Output is correct
7 Correct 472 ms 122256 KB Output is correct
8 Correct 288 ms 120276 KB Output is correct
9 Correct 1235 ms 155968 KB Output is correct
10 Correct 517 ms 135452 KB Output is correct
11 Correct 65 ms 76624 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 94440 KB Output is correct
2 Correct 959 ms 141172 KB Output is correct
3 Correct 1022 ms 144604 KB Output is correct
4 Correct 1069 ms 157632 KB Output is correct
5 Correct 1381 ms 160364 KB Output is correct
6 Correct 1362 ms 157248 KB Output is correct
7 Correct 472 ms 122256 KB Output is correct
8 Correct 288 ms 120276 KB Output is correct
9 Correct 1235 ms 155968 KB Output is correct
10 Correct 517 ms 135452 KB Output is correct
11 Correct 65 ms 76624 KB Output is correct
12 Correct 1022 ms 144532 KB Output is correct
13 Correct 924 ms 157764 KB Output is correct
14 Correct 1385 ms 160688 KB Output is correct
15 Correct 737 ms 140516 KB Output is correct
16 Correct 769 ms 146572 KB Output is correct
17 Correct 886 ms 157544 KB Output is correct
18 Correct 795 ms 140420 KB Output is correct
19 Correct 775 ms 146692 KB Output is correct
20 Correct 557 ms 121164 KB Output is correct
21 Correct 86 ms 83572 KB Output is correct
22 Correct 599 ms 139912 KB Output is correct
23 Correct 520 ms 136268 KB Output is correct
24 Correct 405 ms 124088 KB Output is correct
25 Correct 469 ms 132516 KB Output is correct
26 Correct 339 ms 115536 KB Output is correct
27 Correct 1474 ms 160780 KB Output is correct
28 Correct 738 ms 155528 KB Output is correct
29 Correct 1365 ms 157568 KB Output is correct
30 Correct 504 ms 122396 KB Output is correct
31 Correct 1218 ms 156220 KB Output is correct
32 Correct 387 ms 127372 KB Output is correct
33 Correct 395 ms 126840 KB Output is correct
34 Correct 508 ms 131160 KB Output is correct
35 Correct 459 ms 130980 KB Output is correct
36 Correct 339 ms 124360 KB Output is correct
37 Correct 280 ms 120996 KB Output is correct
38 Correct 256 ms 120384 KB Output is correct
39 Correct 547 ms 129452 KB Output is correct
40 Correct 280 ms 121216 KB Output is correct
41 Correct 291 ms 120864 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70512 KB Output is correct
2 Correct 34 ms 70416 KB Output is correct
3 Correct 29 ms 70488 KB Output is correct
4 Correct 33 ms 70476 KB Output is correct
5 Correct 30 ms 70556 KB Output is correct
6 Correct 30 ms 70544 KB Output is correct
7 Correct 30 ms 70524 KB Output is correct
8 Correct 29 ms 70484 KB Output is correct
9 Correct 30 ms 70484 KB Output is correct
10 Correct 33 ms 70484 KB Output is correct
11 Correct 31 ms 70476 KB Output is correct
12 Correct 31 ms 70484 KB Output is correct
13 Correct 29 ms 70484 KB Output is correct
14 Correct 29 ms 70532 KB Output is correct
15 Correct 30 ms 70432 KB Output is correct
16 Correct 29 ms 70488 KB Output is correct
17 Correct 29 ms 70480 KB Output is correct
18 Correct 29 ms 70472 KB Output is correct
19 Correct 28 ms 70484 KB Output is correct
20 Correct 648 ms 128284 KB Output is correct
21 Correct 601 ms 140504 KB Output is correct
22 Correct 436 ms 126344 KB Output is correct
23 Correct 434 ms 123660 KB Output is correct
24 Correct 424 ms 126612 KB Output is correct
25 Correct 669 ms 131212 KB Output is correct
26 Correct 511 ms 134928 KB Output is correct
27 Incorrect 579 ms 141976 KB Output isn't correct
28 Halted 0 ms 0 KB -