oj.uz

Submission #807767

# Submission time Handle Problem Language Result Execution time Memory
807767 2023-08-05T01:02:28 Z math_rabbit_1028 Sky Walking (IOI19_walk) C++14
43 / 100
 1553 ms 160740 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(tar);
				xmset.erase(-tar);
			}
			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: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: In function 'void get_updn()':
walk.cpp:91: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]
   91 |  for (int i = 0; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |    for (int j = 0; j < add[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |    for (int j = 0; j < rem[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void print_vertex()':
walk.cpp:131: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]
  131 |  for (int i = 0; i < vertex.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_updn()':
walk.cpp:142: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]
  142 |  for (int i = 0; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |    for (int j = 0; j < add[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |    for (int j = 0; j < rem[p].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void link_walk()':
walk.cpp:199: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]
  199 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:204:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |   for (int j = 1; j < xlist[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'void link_sted()':
walk.cpp:219: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]
  219 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:227: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]
  227 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void print_adj()':
walk.cpp:236: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]
  236 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:237: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]
  237 |   for (int j = 0; j < adj[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void dijkstra()':
walk.cpp:256: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]
  256 |   for (int i = 0; i < adj[now].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
walk.cpp: In function 'void print_dis()':
walk.cpp:267: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]
  267 |  for (int i = 0; i < vertex.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70484 KB Output is correct
2 Correct 33 ms 70436 KB Output is correct
3 Correct 33 ms 70540 KB Output is correct
4 Correct 34 ms 70404 KB Output is correct
5 Correct 40 ms 70476 KB Output is correct
6 Correct 34 ms 70444 KB Output is correct
7 Correct 33 ms 70496 KB Output is correct
8 Correct 33 ms 70484 KB Output is correct
9 Correct 32 ms 70432 KB Output is correct
10 Correct 33 ms 70504 KB Output is correct
11 Correct 32 ms 70484 KB Output is correct
12 Correct 33 ms 70484 KB Output is correct
13 Correct 32 ms 70528 KB Output is correct
14 Correct 32 ms 70540 KB Output is correct
15 Correct 33 ms 70496 KB Output is correct
16 Correct 33 ms 70484 KB Output is correct
17 Correct 36 ms 70532 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70448 KB Output is correct
2 Correct 32 ms 70464 KB Output is correct
3 Correct 644 ms 128156 KB Output is correct
4 Correct 563 ms 140436 KB Output is correct
5 Correct 444 ms 126264 KB Output is correct
6 Correct 426 ms 123716 KB Output is correct
7 Correct 427 ms 126500 KB Output is correct
8 Correct 682 ms 131344 KB Output is correct
9 Correct 513 ms 134844 KB Output is correct
10 Incorrect 582 ms 141768 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 194 ms 94444 KB Output is correct
2 Correct 991 ms 141088 KB Output is correct
3 Correct 1030 ms 144428 KB Output is correct
4 Correct 1093 ms 157600 KB Output is correct
5 Correct 1380 ms 160392 KB Output is correct
6 Correct 1362 ms 157296 KB Output is correct
7 Correct 488 ms 122196 KB Output is correct
8 Correct 284 ms 120236 KB Output is correct
9 Correct 1207 ms 155884 KB Output is correct
10 Correct 519 ms 135408 KB Output is correct
11 Correct 57 ms 76500 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 94444 KB Output is correct
2 Correct 991 ms 141088 KB Output is correct
3 Correct 1030 ms 144428 KB Output is correct
4 Correct 1093 ms 157600 KB Output is correct
5 Correct 1380 ms 160392 KB Output is correct
6 Correct 1362 ms 157296 KB Output is correct
7 Correct 488 ms 122196 KB Output is correct
8 Correct 284 ms 120236 KB Output is correct
9 Correct 1207 ms 155884 KB Output is correct
10 Correct 519 ms 135408 KB Output is correct
11 Correct 57 ms 76500 KB Output is correct
12 Correct 1022 ms 144372 KB Output is correct
13 Correct 948 ms 157636 KB Output is correct
14 Correct 1404 ms 160740 KB Output is correct
15 Correct 746 ms 140336 KB Output is correct
16 Correct 792 ms 146508 KB Output is correct
17 Correct 909 ms 157604 KB Output is correct
18 Correct 771 ms 140468 KB Output is correct
19 Correct 809 ms 146460 KB Output is correct
20 Correct 543 ms 121080 KB Output is correct
21 Correct 90 ms 83628 KB Output is correct
22 Correct 596 ms 139852 KB Output is correct
23 Correct 527 ms 136092 KB Output is correct
24 Correct 411 ms 123920 KB Output is correct
25 Correct 469 ms 132496 KB Output is correct
26 Correct 347 ms 115404 KB Output is correct
27 Correct 1553 ms 160716 KB Output is correct
28 Correct 751 ms 155428 KB Output is correct
29 Correct 1375 ms 157484 KB Output is correct
30 Correct 501 ms 122288 KB Output is correct
31 Correct 1237 ms 156048 KB Output is correct
32 Correct 426 ms 127320 KB Output is correct
33 Correct 379 ms 126904 KB Output is correct
34 Correct 546 ms 131044 KB Output is correct
35 Correct 472 ms 131120 KB Output is correct
36 Correct 381 ms 124332 KB Output is correct
37 Correct 289 ms 120884 KB Output is correct
38 Correct 262 ms 120236 KB Output is correct
39 Correct 560 ms 129328 KB Output is correct
40 Correct 282 ms 121132 KB Output is correct
41 Correct 296 ms 120776 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70484 KB Output is correct
2 Correct 33 ms 70436 KB Output is correct
3 Correct 33 ms 70540 KB Output is correct
4 Correct 34 ms 70404 KB Output is correct
5 Correct 40 ms 70476 KB Output is correct
6 Correct 34 ms 70444 KB Output is correct
7 Correct 33 ms 70496 KB Output is correct
8 Correct 33 ms 70484 KB Output is correct
9 Correct 32 ms 70432 KB Output is correct
10 Correct 33 ms 70504 KB Output is correct
11 Correct 32 ms 70484 KB Output is correct
12 Correct 33 ms 70484 KB Output is correct
13 Correct 32 ms 70528 KB Output is correct
14 Correct 32 ms 70540 KB Output is correct
15 Correct 33 ms 70496 KB Output is correct
16 Correct 33 ms 70484 KB Output is correct
17 Correct 36 ms 70532 KB Output is correct
18 Correct 33 ms 70448 KB Output is correct
19 Correct 32 ms 70464 KB Output is correct
20 Correct 644 ms 128156 KB Output is correct
21 Correct 563 ms 140436 KB Output is correct
22 Correct 444 ms 126264 KB Output is correct
23 Correct 426 ms 123716 KB Output is correct
24 Correct 427 ms 126500 KB Output is correct
25 Correct 682 ms 131344 KB Output is correct
26 Correct 513 ms 134844 KB Output is correct
27 Incorrect 582 ms 141768 KB Output isn't correct
28 Halted 0 ms 0 KB -