oj.uz

Submission #147054

# Submission time Handle Problem Language Result Execution time Memory
147054 2019-08-27T10:26:27 Z gs14004 Sky Walking (IOI19_walk) C++17
100 / 100
 2085 ms 171680 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
using pi = pair<lint, int>;
const int MAXN = 100005;
const int MAXV = 2000005;

struct intv{
	int s, e, x;
	bool operator<(const intv &i)const{
		return x < i.x;
	}
};

struct point{
	int x, y, idx;
};

int n, m;
vector<int> witness[MAXN];
vector<pi> event[MAXN];
vector<pi> gph[MAXV];
lint dist[MAXV];

lint dijkstra(int s, int e){
	priority_queue<pi, vector<pi>, greater<pi> > pq;
	memset(dist, 0x3f, sizeof(dist));
	dist[s] = 0;
	pq.emplace(0, s);
	while(!pq.empty()){
		auto x = pq.top();
		pq.pop();
		if(dist[x.second] != x.first) continue;
		for(auto &j : gph[x.second]){
			if(dist[j.second] > x.first + j.first){
				dist[j.second] = x.first + j.first;
				pq.emplace(dist[j.second], j.second);
			}
		}
	}
	if(dist[e] > 1e17) return -1;
	return dist[e];
}

void add_edge(point x, point y){
	int dist = abs(x.x - y.x) + abs(x.y - y.y);
	gph[x.idx].emplace_back(dist, y.idx);
	gph[y.idx].emplace_back(dist, x.idx);
}

void make_vertex(vector<intv> v){
	for(auto &i : v){
		event[i.s].emplace_back(i.x, +1);
		event[i.e+1].emplace_back(i.x, -1);
	}
	multiset<int> swp;
	for(int i=0; i<n; i++){
		for(auto &j : event[i]){
			if(j.second == +1) swp.insert(j.first);
			else swp.erase(swp.find(j.first));
		}
		vector<int> nxt = witness[i];
		for(auto &j : witness[i]){
			if(j == 0) continue;
			auto l = swp.upper_bound(j);
			if(l != swp.end()) nxt.push_back(*l);
			l = swp.lower_bound(j);
			if(l != swp.begin()) nxt.push_back(*prev(l));
		}
		sort(nxt.begin(), nxt.end());
		nxt.resize(unique(nxt.begin(), nxt.end()) - nxt.begin());
		witness[i] = nxt;
	}
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int e) {
	n = sz(x);
	m = sz(l);
	for(int i=0; i<m; i++){
		witness[l[i]].push_back(y[i]);
		witness[r[i]].push_back(y[i]);
	}
	witness[s].push_back(0);
	witness[e].push_back(0);
	vector<pi> points;
	vector<intv> hors;
	set<int> alive;
	for(int i=0; i<n; i++){
		points.emplace_back(h[i], i);
		alive.insert(i);
	}
	for(int i=0; i<m; i++) hors.push_back({l[i], r[i], y[i]});
	sort(points.begin(), points.end());
	sort(hors.begin(), hors.end());
	int ptr = 0;
	for(auto &i : hors){
		while(ptr < sz(points) && points[ptr].first < i.x){
			alive.erase(points[ptr++].second);
		}
		if(i.s <= s && s <= i.e){
			auto it = alive.lower_bound(s);
			witness[*it].push_back(i.x);
			if(*it != s) witness[*prev(it)].push_back(i.x);
		}
		if(i.s <= e && e <= i.e){
			auto it = alive.lower_bound(e);
			witness[*it].push_back(i.x);
			if(*it != e) witness[*prev(it)].push_back(i.x);
		}
	}
	make_vertex(hors);
	vector<point> ans;
	for(int i=0; i<n; i++){
		for(auto &j : witness[i]){
			int num = ans.size();
			ans.push_back({x[i], j, num});
		}
	}
	auto cmpx = [&](const point &x, const point &y) { return pi(x.x, x.y) < pi(y.x, y.y); };
	auto cmpy = [&](const point &x, const point &y) { return pi(x.y, x.x) < pi(y.y, y.x); };
	sort(ans.begin(), ans.end(), cmpx);
	for(int i=0; i<n; i++){
		int st = lower_bound(ans.begin(), ans.end(), (point){x[i], 0, -1}, cmpx) - ans.begin();
		int ed = upper_bound(ans.begin(), ans.end(), (point){x[i], h[i], -1}, cmpx) - ans.begin();
		for(int j=st+1; j<ed; j++){
			add_edge(ans[j-1], ans[j]);
		}
	}
	sort(ans.begin(), ans.end(), cmpy);
	for(int i=0; i<m; i++){
		int st = lower_bound(ans.begin(), ans.end(), (point){x[l[i]], y[i], -1}, cmpy) - ans.begin();
		int ed = upper_bound(ans.begin(), ans.end(), (point){x[r[i]], y[i], -1}, cmpy) - ans.begin();
		for(int j=st+1; j<ed; j++){
			add_edge(ans[j-1], ans[j]);
		}
	}
	s = lower_bound(ans.begin(), ans.end(), (point){x[s], 0, -1}, cmpy)->idx;
	e = lower_bound(ans.begin(), ans.end(), (point){x[e], 0, -1}, cmpy)->idx;
	return dijkstra(s, e);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 67656 KB Output is correct
2 Correct 64 ms 67724 KB Output is correct
3 Correct 76 ms 67576 KB Output is correct
4 Correct 65 ms 67704 KB Output is correct
5 Correct 67 ms 67704 KB Output is correct
6 Correct 74 ms 67752 KB Output is correct
7 Correct 65 ms 67736 KB Output is correct
8 Correct 66 ms 67704 KB Output is correct
9 Correct 64 ms 67664 KB Output is correct
10 Correct 65 ms 67668 KB Output is correct
11 Correct 64 ms 67576 KB Output is correct
12 Correct 64 ms 67676 KB Output is correct
13 Correct 64 ms 67584 KB Output is correct
14 Correct 64 ms 67704 KB Output is correct
15 Correct 64 ms 67676 KB Output is correct
16 Correct 64 ms 67576 KB Output is correct
17 Correct 65 ms 67704 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 67576 KB Output is correct
2 Correct 64 ms 67860 KB Output is correct
3 Correct 988 ms 121040 KB Output is correct
4 Correct 945 ms 125996 KB Output is correct
5 Correct 619 ms 115380 KB Output is correct
6 Correct 630 ms 112288 KB Output is correct
7 Correct 637 ms 115516 KB Output is correct
8 Correct 945 ms 127048 KB Output is correct
9 Correct 784 ms 123328 KB Output is correct
10 Correct 984 ms 130256 KB Output is correct
11 Correct 775 ms 112932 KB Output is correct
12 Correct 556 ms 98088 KB Output is correct
13 Correct 1025 ms 131156 KB Output is correct
14 Correct 631 ms 103084 KB Output is correct
15 Correct 631 ms 104812 KB Output is correct
16 Correct 585 ms 104924 KB Output is correct
17 Correct 593 ms 103768 KB Output is correct
18 Correct 790 ms 106124 KB Output is correct
19 Correct 79 ms 69320 KB Output is correct
20 Correct 244 ms 85100 KB Output is correct
21 Correct 469 ms 101476 KB Output is correct
22 Correct 549 ms 103396 KB Output is correct
23 Correct 760 ms 111820 KB Output is correct
24 Correct 557 ms 103816 KB Output is correct
25 Correct 553 ms 102676 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 79776 KB Output is correct
2 Correct 1161 ms 136968 KB Output is correct
3 Correct 1232 ms 142132 KB Output is correct
4 Correct 1293 ms 151500 KB Output is correct
5 Correct 1564 ms 154140 KB Output is correct
6 Correct 1480 ms 147552 KB Output is correct
7 Correct 693 ms 115784 KB Output is correct
8 Correct 497 ms 103016 KB Output is correct
9 Correct 1362 ms 141744 KB Output is correct
10 Correct 696 ms 115568 KB Output is correct
11 Correct 96 ms 72300 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 79776 KB Output is correct
2 Correct 1161 ms 136968 KB Output is correct
3 Correct 1232 ms 142132 KB Output is correct
4 Correct 1293 ms 151500 KB Output is correct
5 Correct 1564 ms 154140 KB Output is correct
6 Correct 1480 ms 147552 KB Output is correct
7 Correct 693 ms 115784 KB Output is correct
8 Correct 497 ms 103016 KB Output is correct
9 Correct 1362 ms 141744 KB Output is correct
10 Correct 696 ms 115568 KB Output is correct
11 Correct 96 ms 72300 KB Output is correct
12 Correct 1220 ms 141608 KB Output is correct
13 Correct 1123 ms 145880 KB Output is correct
14 Correct 1801 ms 149580 KB Output is correct
15 Correct 1058 ms 134368 KB Output is correct
16 Correct 1121 ms 133476 KB Output is correct
17 Correct 1288 ms 146792 KB Output is correct
18 Correct 1104 ms 134588 KB Output is correct
19 Correct 1114 ms 133160 KB Output is correct
20 Correct 780 ms 110232 KB Output is correct
21 Correct 200 ms 77672 KB Output is correct
22 Correct 829 ms 129364 KB Output is correct
23 Correct 764 ms 125788 KB Output is correct
24 Correct 626 ms 109544 KB Output is correct
25 Correct 713 ms 121308 KB Output is correct
26 Correct 549 ms 102920 KB Output is correct
27 Correct 1442 ms 151244 KB Output is correct
28 Correct 1048 ms 145288 KB Output is correct
29 Correct 1517 ms 143048 KB Output is correct
30 Correct 743 ms 111088 KB Output is correct
31 Correct 1407 ms 137600 KB Output is correct
32 Correct 570 ms 109108 KB Output is correct
33 Correct 596 ms 108540 KB Output is correct
34 Correct 729 ms 113344 KB Output is correct
35 Correct 721 ms 114268 KB Output is correct
36 Correct 695 ms 106716 KB Output is correct
37 Correct 474 ms 102020 KB Output is correct
38 Correct 606 ms 103852 KB Output is correct
39 Correct 793 ms 112200 KB Output is correct
40 Correct 550 ms 104280 KB Output is correct
41 Correct 549 ms 102844 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 67656 KB Output is correct
2 Correct 64 ms 67724 KB Output is correct
3 Correct 76 ms 67576 KB Output is correct
4 Correct 65 ms 67704 KB Output is correct
5 Correct 67 ms 67704 KB Output is correct
6 Correct 74 ms 67752 KB Output is correct
7 Correct 65 ms 67736 KB Output is correct
8 Correct 66 ms 67704 KB Output is correct
9 Correct 64 ms 67664 KB Output is correct
10 Correct 65 ms 67668 KB Output is correct
11 Correct 64 ms 67576 KB Output is correct
12 Correct 64 ms 67676 KB Output is correct
13 Correct 64 ms 67584 KB Output is correct
14 Correct 64 ms 67704 KB Output is correct
15 Correct 64 ms 67676 KB Output is correct
16 Correct 64 ms 67576 KB Output is correct
17 Correct 65 ms 67704 KB Output is correct
18 Correct 64 ms 67576 KB Output is correct
19 Correct 64 ms 67860 KB Output is correct
20 Correct 988 ms 121040 KB Output is correct
21 Correct 945 ms 125996 KB Output is correct
22 Correct 619 ms 115380 KB Output is correct
23 Correct 630 ms 112288 KB Output is correct
24 Correct 637 ms 115516 KB Output is correct
25 Correct 945 ms 127048 KB Output is correct
26 Correct 784 ms 123328 KB Output is correct
27 Correct 984 ms 130256 KB Output is correct
28 Correct 775 ms 112932 KB Output is correct
29 Correct 556 ms 98088 KB Output is correct
30 Correct 1025 ms 131156 KB Output is correct
31 Correct 631 ms 103084 KB Output is correct
32 Correct 631 ms 104812 KB Output is correct
33 Correct 585 ms 104924 KB Output is correct
34 Correct 593 ms 103768 KB Output is correct
35 Correct 790 ms 106124 KB Output is correct
36 Correct 79 ms 69320 KB Output is correct
37 Correct 244 ms 85100 KB Output is correct
38 Correct 469 ms 101476 KB Output is correct
39 Correct 549 ms 103396 KB Output is correct
40 Correct 760 ms 111820 KB Output is correct
41 Correct 557 ms 103816 KB Output is correct
42 Correct 553 ms 102676 KB Output is correct
43 Correct 199 ms 79776 KB Output is correct
44 Correct 1161 ms 136968 KB Output is correct
45 Correct 1232 ms 142132 KB Output is correct
46 Correct 1293 ms 151500 KB Output is correct
47 Correct 1564 ms 154140 KB Output is correct
48 Correct 1480 ms 147552 KB Output is correct
49 Correct 693 ms 115784 KB Output is correct
50 Correct 497 ms 103016 KB Output is correct
51 Correct 1362 ms 141744 KB Output is correct
52 Correct 696 ms 115568 KB Output is correct
53 Correct 96 ms 72300 KB Output is correct
54 Correct 1220 ms 141608 KB Output is correct
55 Correct 1123 ms 145880 KB Output is correct
56 Correct 1801 ms 149580 KB Output is correct
57 Correct 1058 ms 134368 KB Output is correct
58 Correct 1121 ms 133476 KB Output is correct
59 Correct 1288 ms 146792 KB Output is correct
60 Correct 1104 ms 134588 KB Output is correct
61 Correct 1114 ms 133160 KB Output is correct
62 Correct 780 ms 110232 KB Output is correct
63 Correct 200 ms 77672 KB Output is correct
64 Correct 829 ms 129364 KB Output is correct
65 Correct 764 ms 125788 KB Output is correct
66 Correct 626 ms 109544 KB Output is correct
67 Correct 713 ms 121308 KB Output is correct
68 Correct 549 ms 102920 KB Output is correct
69 Correct 1442 ms 151244 KB Output is correct
70 Correct 1048 ms 145288 KB Output is correct
71 Correct 1517 ms 143048 KB Output is correct
72 Correct 743 ms 111088 KB Output is correct
73 Correct 1407 ms 137600 KB Output is correct
74 Correct 570 ms 109108 KB Output is correct
75 Correct 596 ms 108540 KB Output is correct
76 Correct 729 ms 113344 KB Output is correct
77 Correct 721 ms 114268 KB Output is correct
78 Correct 695 ms 106716 KB Output is correct
79 Correct 474 ms 102020 KB Output is correct
80 Correct 606 ms 103852 KB Output is correct
81 Correct 793 ms 112200 KB Output is correct
82 Correct 550 ms 104280 KB Output is correct
83 Correct 549 ms 102844 KB Output is correct
84 Correct 183 ms 77716 KB Output is correct
85 Correct 1293 ms 143000 KB Output is correct
86 Correct 1783 ms 158832 KB Output is correct
87 Correct 192 ms 82792 KB Output is correct
88 Correct 246 ms 79872 KB Output is correct
89 Correct 220 ms 82628 KB Output is correct
90 Correct 118 ms 72048 KB Output is correct
91 Correct 78 ms 67832 KB Output is correct
92 Correct 115 ms 70932 KB Output is correct
93 Correct 553 ms 98548 KB Output is correct
94 Correct 202 ms 77800 KB Output is correct
95 Correct 937 ms 132688 KB Output is correct
96 Correct 781 ms 126044 KB Output is correct
97 Correct 637 ms 109660 KB Output is correct
98 Correct 710 ms 121372 KB Output is correct
99 Correct 2085 ms 171680 KB Output is correct
100 Correct 1344 ms 146764 KB Output is correct
101 Correct 1650 ms 150356 KB Output is correct
102 Correct 754 ms 111348 KB Output is correct
103 Correct 602 ms 105820 KB Output is correct
104 Correct 581 ms 106188 KB Output is correct
105 Correct 684 ms 109992 KB Output is correct
106 Correct 645 ms 107252 KB Output is correct
107 Correct 701 ms 108956 KB Output is correct
108 Correct 131 ms 73756 KB Output is correct
109 Correct 1194 ms 130268 KB Output is correct
110 Correct 1084 ms 145356 KB Output is correct
111 Correct 1120 ms 144812 KB Output is correct
112 Correct 704 ms 112860 KB Output is correct
113 Correct 686 ms 109624 KB Output is correct