Submission #299519

#	Time	Username	Problem	Language	Result	Execution time	Memory
299519		TMJN	Sky Walking (IOI19_walk)	C++17	0 / 100	46 ms	5196 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

int ud[100000][2];
long long dist[100000];

long long min_distance(vector<int>x,vector<int>h,vector<int>l,vector<int>r,vector<int>y,int s,int g){
	int N,M;
	N=x.size();
	M=l.size();
	assert(s==0&&g==N-1);
	int can_vis=0;
	vector<pair<pair<int,int>,int>>p(M);
	for(int i=0;i<M;i++){
		p[i]={{l[i],r[i]},y[i]};
	}
	sort(p.begin(),p.end());
	for(int i=0;i<M;i++){
		if(p[i].first.first<=can_vis){
			can_vis=max(can_vis,p[i].first.second);
		}
	}
	if(can_vis!=N-1)return -1;
	set<pair<int,int>>st;
	st.insert({-1,-1});
	st.insert({1000000007,-1});
	vector<pair<int,int>>rid;
	for(int i=0;i<M;i++){
		rid.push_back({p[i].first.second,i});
		ud[i][0]=ud[i][1]=-1;
		dist[i]=-1;
	}
	sort(rid.begin(),rid.end());
	int pp=0;
	for(int i=0;i<M;i++){
		for(;rid[pp].first<p[i].first.first;pp++){
			st.erase({y[rid[pp].second],rid[pp].second});
			auto it=st.lower_bound({y[rid[pp].second],-1});
			ud[rid[pp].second][0]=it->second;
			it--;
			ud[rid[pp].second][1]=it->second;
		}
		st.insert({p[i].second,i});
	}
	for(;pp<M;pp++){
		st.erase({y[rid[pp].second],rid[pp].second});
		auto it=st.lower_bound({y[rid[pp].second],-1});
		ud[rid[pp].second][0]=it->second;
		it--;
		ud[rid[pp].second][1]=it->second;
	}
	priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;
	for(int i=0;i<M;i++){
		if(p[i].first.first==0){
			pq.push({p[i].second,i});
		}
	}
	while(!pq.empty()){
		long long l=pq.top().first;
		int t=pq.top().second;
		pq.pop();
		if(dist[t]==-1){
			dist[t]=l;
			for(int i=0;i<2;i++){
				if(ud[t][i]!=-1){
					pq.push({l+abs(p[t].second-p[ud[t][i]].second),ud[t][i]});
				}
			}
		}
	}
	long long mn=0xE869120E869120;
	for(int i=0;i<M;i++){
		if(p[i].first.second==N-1&&dist[i]!=-1){
			mn=min(mn,dist[i]+p[i].second);
		}
	}
	return mn+x[N-1]-x[0];
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43