제출 #210271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210271		Segtree	Sky Walking (IOI19_walk)	C++14	15 / 100	234 ms	23348 KiB

walk

#include"walk.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cassert>
#include<stack>
#include<fstream>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
typedef struct st{
	ll height,eid;
	bool operator<(const st&key)const{
		if(this->height==key.height)return this->eid<key.eid;
		return this->height<key.height;
	}
	bool operator==(const st&key)const{
		return this->eid==key.eid;
	}
}st;
ll min_distance(vector<int> x,vector<int> h,vector<int> l,vector<int> r,vector<int> y,int s,int g){
	int n=x.size(),m=l.size();
	set<st> S;
	S.insert((st){0,m});
	ll dp[100010];
	rep(i,m)dp[i]=1e17;
	dp[m]=0;
	vector<ll> app[100010],disapp[100010];
	rep(i,m){
		app[l[i]].push_back(i);
		disapp[r[i]].push_back(i);
	}
	disapp[0].push_back(m);
	rep(i,n){
		for(auto id:app[i])S.insert((st){y[id],id});
		for(auto id:disapp[i])S.erase((st){y[id],id});
		//cerr<<"S.size()="<<i<<" "<<S.size()<<endl;
		for(auto id:disapp[i]){
			auto it=S.lower_bound((st){y[id],id});
			if(it!=S.end()){
				//cerr<<"dp:"<<it->eid<<" "<<id<<endl;
				chmin(dp[it->eid],dp[id]+abs(y[id]-it->height));
			}
			if(it!=S.begin()){
				it--;
				//cerr<<"dp:"<<it->eid<<" "<<id<<endl;
				chmin(dp[it->eid],dp[id]+abs(y[id]-it->height));
			}
		}
	}
	ll ans=1e17;
	for(auto id:disapp[n-1])chmin(ans,dp[id]+y[id]);
	if(ans==1e17)return -1;
	ans+=x[n-1]-x[0];
	return ans;
}/*
int main(){
	int n,m,s,g;
	cin>>n>>m;
	vector<int> x(n),h(n),l(m),r(m),y(m);
	rep(i,n)cin>>x[i]>>h[i];
	rep(i,m)cin>>l[i]>>r[i]>>y[i];
	cin>>s>>g;
	cout<<min_distance(x,h,l,r,y,s,g)<<endl;
}*/

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