oj.uz

Submission #286595

# Submission time Handle Problem Language Result Execution time Memory
286595 2020-08-30T15:11:40 Z tmwilliamlin168 Sky Walking (IOI19_walk) C++14
100 / 100
 1971 ms 141372 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5, mxT=1e6;
int n, m, pg[mxN], t, ua, ub;
vector<int> ta[mxN], tr[mxN];
ll d[mxT];
vector<ar<ll, 2>> adj[mxT];

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int a, int b) {
	n=x.size();
	m=l.size();
	vector<vector<int>> v(n);
	v[a].push_back(0);
	v[b].push_back(0);
	for(int _ : {1, 0}) {
		for(int i=0; i<m; ++i) {
			ta[l[i]].push_back(i);
			tr[r[i]].push_back(i);
		}
		set<ar<int, 2>> s;
		for(int i=0; i<n; ++i) {
			vector<ar<int, 2>> w;
			for(pg[i]=i-1; ~pg[i]&&h[pg[i]]<=h[i]; pg[i]=pg[pg[i]]) {
				auto it=s.lower_bound({h[pg[i]]});
				if(it!=s.end()&&(*it)[0]<=h[i])
					w.push_back(*it);
			}
			for(int j : ta[i])
				s.insert({y[j], j});
			for(auto a : w) {
				v[i].push_back(a[0]);
				auto it=s.upper_bound(a);
				if(it!=s.end()&&(*it)[0]<=h[i])
					v[i].push_back((*it)[0]);
			}
			for(int j : ta[i]) {
				v[i].push_back(y[j]);
				auto it=s.upper_bound({y[j], j});
				if(it!=s.end()&&(*it)[0]<=h[i])
					v[i].push_back((*it)[0]);
				if(--it!=s.begin())
					v[i].push_back((*--it)[0]);
			}
			if(_&&(i==a||i==b)&&s.size()&&(*s.begin())[0]<=h[i])
				v[i].push_back((*s.begin())[0]);
			for(int j : tr[i])
				s.erase({y[j], j});
			ta[i].clear();
			tr[i].clear();
		}
		reverse(h.begin(), h.end());
		for(int i=0; i<m; ++i)
			tie(l[i], r[i])=make_pair(n-1-r[i], n-1-l[i]);
		reverse(v.begin(), v.end());
	}
	unordered_map<int, int> m1;
	unordered_map<int, ar<int, 3>> m2;
	for(int i=0; i<m; ++i)
		ta[l[i]].push_back(i);
	for(int i=0; i<n; t+=v[i++].size()) {
		if(i==a)
			ua=t;
		if(i==b)
			ub=t;
		for(int j : ta[i])
			m1[y[j]]=r[j]+1;
		sort(v[i].begin(), v[i].end());
		v[i].resize(unique(v[i].begin(), v[i].end())-v[i].begin());
		for(int j=0; j+1<v[i].size(); ++j) {
			adj[t+j].push_back({v[i][j+1]-v[i][j], t+j+1});
			adj[t+j+1].push_back({v[i][j+1]-v[i][j], t+j});
		}
		for(int j=0; j<v[i].size(); ++j) {
			auto a=m2[v[i][j]];
			if(a[2]>i) {
				adj[a[0]].push_back({x[i]-x[a[1]], t+j});
				adj[t+j].push_back({x[i]-x[a[1]], a[0]});
			}
			m2[v[i][j]]={t+j, i, m1[v[i][j]]};
		}
	}
	memset(d, 0x3f, 8*t);
	priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>>> pq;
	d[ua]=0;
	pq.push({0, ua});
	while(pq.size()) {
		ar<ll, 2> u=pq.top();
		pq.pop();
		if(u[0]>d[u[1]])
			continue;
		for(auto v : adj[u[1]]) {
			if(d[v[1]]>u[0]+v[0]) {
				d[v[1]]=u[0]+v[0];
				pq.push({d[v[1]], v[1]});
			}
		}
	}
	return d[ub]>2e14?-1:d[ub];
}

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int j=0; j+1<v[i].size(); ++j) {
      |                ~~~^~~~~~~~~~~~
walk.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int j=0; j<v[i].size(); ++j) {
      |                ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28544 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 20 ms 28544 KB Output is correct
4 Correct 20 ms 28544 KB Output is correct
5 Correct 20 ms 28544 KB Output is correct
6 Correct 20 ms 28544 KB Output is correct
7 Correct 20 ms 28544 KB Output is correct
8 Correct 20 ms 28544 KB Output is correct
9 Correct 19 ms 28544 KB Output is correct
10 Correct 20 ms 28544 KB Output is correct
11 Correct 20 ms 28544 KB Output is correct
12 Correct 19 ms 28544 KB Output is correct
13 Correct 20 ms 28544 KB Output is correct
14 Correct 20 ms 28544 KB Output is correct
15 Correct 20 ms 28544 KB Output is correct
16 Correct 19 ms 28544 KB Output is correct
17 Correct 20 ms 28544 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28544 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 526 ms 81984 KB Output is correct
4 Correct 649 ms 93248 KB Output is correct
5 Correct 433 ms 76864 KB Output is correct
6 Correct 448 ms 73536 KB Output is correct
7 Correct 439 ms 77124 KB Output is correct
8 Correct 589 ms 86720 KB Output is correct
9 Correct 561 ms 89192 KB Output is correct
10 Correct 733 ms 102208 KB Output is correct
11 Correct 480 ms 74432 KB Output is correct
12 Correct 394 ms 64192 KB Output is correct
13 Correct 659 ms 98216 KB Output is correct
14 Correct 472 ms 63752 KB Output is correct
15 Correct 392 ms 60536 KB Output is correct
16 Correct 308 ms 59000 KB Output is correct
17 Correct 325 ms 57848 KB Output is correct
18 Correct 450 ms 67164 KB Output is correct
19 Correct 34 ms 30328 KB Output is correct
20 Correct 196 ms 45768 KB Output is correct
21 Correct 272 ms 56440 KB Output is correct
22 Correct 290 ms 57464 KB Output is correct
23 Correct 471 ms 70372 KB Output is correct
24 Correct 296 ms 58232 KB Output is correct
25 Correct 297 ms 57476 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 38264 KB Output is correct
2 Correct 754 ms 95100 KB Output is correct
3 Correct 800 ms 96960 KB Output is correct
4 Correct 1010 ms 106748 KB Output is correct
5 Correct 1279 ms 106908 KB Output is correct
6 Correct 1202 ms 103844 KB Output is correct
7 Correct 464 ms 72364 KB Output is correct
8 Correct 377 ms 64192 KB Output is correct
9 Correct 1091 ms 102284 KB Output is correct
10 Correct 388 ms 72432 KB Output is correct
11 Correct 40 ms 31000 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 38264 KB Output is correct
2 Correct 754 ms 95100 KB Output is correct
3 Correct 800 ms 96960 KB Output is correct
4 Correct 1010 ms 106748 KB Output is correct
5 Correct 1279 ms 106908 KB Output is correct
6 Correct 1202 ms 103844 KB Output is correct
7 Correct 464 ms 72364 KB Output is correct
8 Correct 377 ms 64192 KB Output is correct
9 Correct 1091 ms 102284 KB Output is correct
10 Correct 388 ms 72432 KB Output is correct
11 Correct 40 ms 31000 KB Output is correct
12 Correct 806 ms 100160 KB Output is correct
13 Correct 1010 ms 137796 KB Output is correct
14 Correct 1794 ms 140988 KB Output is correct
15 Correct 782 ms 88200 KB Output is correct
16 Correct 1148 ms 122124 KB Output is correct
17 Correct 1234 ms 133388 KB Output is correct
18 Correct 794 ms 88456 KB Output is correct
19 Correct 1125 ms 121228 KB Output is correct
20 Correct 801 ms 102928 KB Output is correct
21 Correct 280 ms 59512 KB Output is correct
22 Correct 544 ms 94340 KB Output is correct
23 Correct 492 ms 85312 KB Output is correct
24 Correct 467 ms 70976 KB Output is correct
25 Correct 468 ms 82036 KB Output is correct
26 Correct 476 ms 63808 KB Output is correct
27 Correct 1720 ms 133952 KB Output is correct
28 Correct 807 ms 137664 KB Output is correct
29 Correct 1715 ms 138992 KB Output is correct
30 Correct 720 ms 98832 KB Output is correct
31 Correct 1609 ms 134684 KB Output is correct
32 Correct 320 ms 63600 KB Output is correct
33 Correct 336 ms 65136 KB Output is correct
34 Correct 419 ms 69768 KB Output is correct
35 Correct 497 ms 75340 KB Output is correct
36 Correct 335 ms 63216 KB Output is correct
37 Correct 269 ms 56440 KB Output is correct
38 Correct 279 ms 57336 KB Output is correct
39 Correct 467 ms 70372 KB Output is correct
40 Correct 287 ms 58184 KB Output is correct
41 Correct 295 ms 57464 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28544 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 20 ms 28544 KB Output is correct
4 Correct 20 ms 28544 KB Output is correct
5 Correct 20 ms 28544 KB Output is correct
6 Correct 20 ms 28544 KB Output is correct
7 Correct 20 ms 28544 KB Output is correct
8 Correct 20 ms 28544 KB Output is correct
9 Correct 19 ms 28544 KB Output is correct
10 Correct 20 ms 28544 KB Output is correct
11 Correct 20 ms 28544 KB Output is correct
12 Correct 19 ms 28544 KB Output is correct
13 Correct 20 ms 28544 KB Output is correct
14 Correct 20 ms 28544 KB Output is correct
15 Correct 20 ms 28544 KB Output is correct
16 Correct 19 ms 28544 KB Output is correct
17 Correct 20 ms 28544 KB Output is correct
18 Correct 19 ms 28544 KB Output is correct
19 Correct 19 ms 28544 KB Output is correct
20 Correct 526 ms 81984 KB Output is correct
21 Correct 649 ms 93248 KB Output is correct
22 Correct 433 ms 76864 KB Output is correct
23 Correct 448 ms 73536 KB Output is correct
24 Correct 439 ms 77124 KB Output is correct
25 Correct 589 ms 86720 KB Output is correct
26 Correct 561 ms 89192 KB Output is correct
27 Correct 733 ms 102208 KB Output is correct
28 Correct 480 ms 74432 KB Output is correct
29 Correct 394 ms 64192 KB Output is correct
30 Correct 659 ms 98216 KB Output is correct
31 Correct 472 ms 63752 KB Output is correct
32 Correct 392 ms 60536 KB Output is correct
33 Correct 308 ms 59000 KB Output is correct
34 Correct 325 ms 57848 KB Output is correct
35 Correct 450 ms 67164 KB Output is correct
36 Correct 34 ms 30328 KB Output is correct
37 Correct 196 ms 45768 KB Output is correct
38 Correct 272 ms 56440 KB Output is correct
39 Correct 290 ms 57464 KB Output is correct
40 Correct 471 ms 70372 KB Output is correct
41 Correct 296 ms 58232 KB Output is correct
42 Correct 297 ms 57476 KB Output is correct
43 Correct 112 ms 38264 KB Output is correct
44 Correct 754 ms 95100 KB Output is correct
45 Correct 800 ms 96960 KB Output is correct
46 Correct 1010 ms 106748 KB Output is correct
47 Correct 1279 ms 106908 KB Output is correct
48 Correct 1202 ms 103844 KB Output is correct
49 Correct 464 ms 72364 KB Output is correct
50 Correct 377 ms 64192 KB Output is correct
51 Correct 1091 ms 102284 KB Output is correct
52 Correct 388 ms 72432 KB Output is correct
53 Correct 40 ms 31000 KB Output is correct
54 Correct 806 ms 100160 KB Output is correct
55 Correct 1010 ms 137796 KB Output is correct
56 Correct 1794 ms 140988 KB Output is correct
57 Correct 782 ms 88200 KB Output is correct
58 Correct 1148 ms 122124 KB Output is correct
59 Correct 1234 ms 133388 KB Output is correct
60 Correct 794 ms 88456 KB Output is correct
61 Correct 1125 ms 121228 KB Output is correct
62 Correct 801 ms 102928 KB Output is correct
63 Correct 280 ms 59512 KB Output is correct
64 Correct 544 ms 94340 KB Output is correct
65 Correct 492 ms 85312 KB Output is correct
66 Correct 467 ms 70976 KB Output is correct
67 Correct 468 ms 82036 KB Output is correct
68 Correct 476 ms 63808 KB Output is correct
69 Correct 1720 ms 133952 KB Output is correct
70 Correct 807 ms 137664 KB Output is correct
71 Correct 1715 ms 138992 KB Output is correct
72 Correct 720 ms 98832 KB Output is correct
73 Correct 1609 ms 134684 KB Output is correct
74 Correct 320 ms 63600 KB Output is correct
75 Correct 336 ms 65136 KB Output is correct
76 Correct 419 ms 69768 KB Output is correct
77 Correct 497 ms 75340 KB Output is correct
78 Correct 335 ms 63216 KB Output is correct
79 Correct 269 ms 56440 KB Output is correct
80 Correct 279 ms 57336 KB Output is correct
81 Correct 467 ms 70372 KB Output is correct
82 Correct 287 ms 58184 KB Output is correct
83 Correct 295 ms 57464 KB Output is correct
84 Correct 96 ms 37240 KB Output is correct
85 Correct 813 ms 99904 KB Output is correct
86 Correct 1819 ms 141372 KB Output is correct
87 Correct 135 ms 43768 KB Output is correct
88 Correct 259 ms 57720 KB Output is correct
89 Correct 136 ms 43768 KB Output is correct
90 Correct 52 ms 33528 KB Output is correct
91 Correct 21 ms 28800 KB Output is correct
92 Correct 61 ms 34296 KB Output is correct
93 Correct 662 ms 90852 KB Output is correct
94 Correct 259 ms 57464 KB Output is correct
95 Correct 590 ms 97472 KB Output is correct
96 Correct 492 ms 85696 KB Output is correct
97 Correct 469 ms 70848 KB Output is correct
98 Correct 476 ms 82116 KB Output is correct
99 Correct 1971 ms 138216 KB Output is correct
100 Correct 1244 ms 140148 KB Output is correct
101 Correct 1835 ms 138456 KB Output is correct
102 Correct 732 ms 99216 KB Output is correct
103 Correct 346 ms 64428 KB Output is correct
104 Correct 327 ms 64884 KB Output is correct
105 Correct 436 ms 69040 KB Output is correct
106 Correct 398 ms 67068 KB Output is correct
107 Correct 441 ms 64944 KB Output is correct
108 Correct 92 ms 37496 KB Output is correct
109 Correct 1381 ms 120980 KB Output is correct
110 Correct 746 ms 118720 KB Output is correct
111 Correct 699 ms 118720 KB Output is correct
112 Correct 463 ms 72160 KB Output is correct
113 Correct 407 ms 67320 KB Output is correct