oj.uz

Submission #1071365

# Submission time Handle Problem Language Result Execution time Memory
1071365 2024-08-23T06:55:56 Z LittleOrange Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 702552 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 1e18;
struct pos{
	ll x,y;
	bool operator<(const pos &o) const{
		return x!=o.x?x<o.x:y<o.y;
	}
	bool operator==(const pos &o) const{
		return x==o.x&&y==o.y;
	}
	bool operator!=(const pos &o) const{
		return x!=o.x||y!=o.y;
	}
};
struct line{
	ll i,v;
	bool operator<(const line &o) const{
		return v>o.v;
	}
};
long long 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) {
	ll n = x.size();
	ll m = y.size();
	vector<pos> ps;
	for(ll i = 0;i<n;i++) ps.push_back({x[i],0});
	{
		vector<pair<ll,ll>> builds,bridges;
		for(ll i = 0;i<n;i++) builds.push_back({h[i],i});
		for(ll i = 0;i<m;i++) bridges.push_back({y[i],i});
		sort(builds.begin(),builds.end());
		sort(bridges.rbegin(),bridges.rend());
		set<ll> s;
		for(auto [yy,i] : bridges){
			while(builds.size()&&(builds.back().first)>=yy){
				s.insert(builds.back().second);
				//cerr << "add build " << builds.back().second << "\n";
				builds.pop_back();
			}
			for(auto it = s.lower_bound(l[i]);it!=s.end()&&(*it)<=r[i];it++){
				//cerr << "add " << x[*it] << ", " << y[i] << "\n";
				ps.push_back({x[*it],y[i]});
			}
		}
	}
	/*for(ll i = 0;i<m;i++){
		for(ll j = l[i];j<=r[i];j++){
			if (h[j]>=y[i]){
				ps.push_back({x[j],y[i]});
			}
		}
	}*/
	sort(ps.begin(),ps.end());
	ps.erase(unique(ps.begin(),ps.end()),ps.end());
	auto gp = [&](pos p){
		return lower_bound(ps.begin(),ps.end(),p)-ps.begin();
	};
	ll c = ps.size();
	vector<vector<line>> con(c);
	for(ll i = 1;i<c;i++){
		if (ps[i-1].x==ps[i].x){
			ll d = ps[i].y-ps[i-1].y;
			con[i-1].push_back({i,d});
			con[i].push_back({i-1,d});
		}
	}
	{
		vector<pair<ll,ll>> builds,bridges;
		for(ll i = 0;i<n;i++) builds.push_back({h[i],i});
		for(ll i = 0;i<m;i++) bridges.push_back({y[i],i});
		sort(builds.begin(),builds.end());
		sort(bridges.rbegin(),bridges.rend());
		set<ll> s;
		for(auto [yy,i] : bridges){
			vector<ll> v;
			while(builds.size()&&(builds.back().first)>=yy){
				s.insert(builds.back().second);
				//cerr << "add build " << builds.back().second << "\n";
				builds.pop_back();
			}
			for(auto it = s.lower_bound(l[i]);it!=s.end()&&(*it)<=r[i];it++){
				//cerr << "add " << x[*it] << ", " << y[i] << "\n";
				v.push_back(gp({x[*it],y[i]}));
			}
			for(ll j = 1;j<v.size();j++){
				ll d = ps[v[j]].x-ps[v[j-1]].x;
				con[v[j-1]].push_back({v[j],d});
				con[v[j]].push_back({v[j-1],d});
			}
		}
	}
	/*for(ll i = 0;i<m;i++){
		vector<ll> v;
		for(ll j = l[i];j<=r[i];j++){
			if (h[j]>=y[i]){
				v.push_back(gp({x[j],y[i]}));
			}
		}
		for(ll j = 1;j<v.size();j++){
			ll d = ps[v[j]].x-ps[v[j-1]].x;
			con[v[j-1]].push_back({v[j],d});
			con[v[j]].push_back({v[j-1],d});
		}
	}*/
	ll start = gp({x[s],0});
	ll goal = gp({x[g],0});
	vector<ll> dis(c,big);
	priority_queue<line> q;
	q.push({start,0});
	while(q.size()){
		auto [i,v] = q.top();q.pop();
		if(dis[i]<=v) continue;
		dis[i] = v;
		for(auto [j,w] : con[i]){
			q.push({j,v+w});
		}
	}
	ll ans = dis[goal];
	if (ans>=big) ans = -1;
	return ans;
}

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:87:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    for(ll j = 1;j<v.size();j++){
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 412 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 926 ms 103316 KB Output is correct
4 Correct 913 ms 117448 KB Output is correct
5 Correct 599 ms 101604 KB Output is correct
6 Correct 493 ms 92864 KB Output is correct
7 Correct 589 ms 103464 KB Output is correct
8 Correct 1121 ms 129952 KB Output is correct
9 Correct 657 ms 99992 KB Output is correct
10 Correct 1338 ms 156048 KB Output is correct
11 Correct 454 ms 60548 KB Output is correct
12 Correct 355 ms 48236 KB Output is correct
13 Correct 1066 ms 136840 KB Output is correct
14 Correct 256 ms 46596 KB Output is correct
15 Correct 244 ms 44392 KB Output is correct
16 Correct 256 ms 45804 KB Output is correct
17 Correct 279 ms 43880 KB Output is correct
18 Correct 161 ms 40296 KB Output is correct
19 Correct 7 ms 2624 KB Output is correct
20 Correct 81 ms 23832 KB Output is correct
21 Correct 251 ms 46580 KB Output is correct
22 Correct 281 ms 42604 KB Output is correct
23 Correct 279 ms 58984 KB Output is correct
24 Correct 258 ms 46300 KB Output is correct
25 Correct 273 ms 44380 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 12828 KB Output is correct
2 Execution timed out 4051 ms 702552 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 12828 KB Output is correct
2 Execution timed out 4051 ms 702552 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 412 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 926 ms 103316 KB Output is correct
21 Correct 913 ms 117448 KB Output is correct
22 Correct 599 ms 101604 KB Output is correct
23 Correct 493 ms 92864 KB Output is correct
24 Correct 589 ms 103464 KB Output is correct
25 Correct 1121 ms 129952 KB Output is correct
26 Correct 657 ms 99992 KB Output is correct
27 Correct 1338 ms 156048 KB Output is correct
28 Correct 454 ms 60548 KB Output is correct
29 Correct 355 ms 48236 KB Output is correct
30 Correct 1066 ms 136840 KB Output is correct
31 Correct 256 ms 46596 KB Output is correct
32 Correct 244 ms 44392 KB Output is correct
33 Correct 256 ms 45804 KB Output is correct
34 Correct 279 ms 43880 KB Output is correct
35 Correct 161 ms 40296 KB Output is correct
36 Correct 7 ms 2624 KB Output is correct
37 Correct 81 ms 23832 KB Output is correct
38 Correct 251 ms 46580 KB Output is correct
39 Correct 281 ms 42604 KB Output is correct
40 Correct 279 ms 58984 KB Output is correct
41 Correct 258 ms 46300 KB Output is correct
42 Correct 273 ms 44380 KB Output is correct
43 Correct 78 ms 12828 KB Output is correct
44 Execution timed out 4051 ms 702552 KB Time limit exceeded
45 Halted 0 ms 0 KB -