Submission #1071365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071365		LittleOrange	Sky Walking (IOI19_walk)	C++17	24 / 100	4051 ms	702552 KiB

walk

#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 (stderr)

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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43