Submission #210269

#	Time	Username	Problem	Language	Result	Execution time	Memory
210269		Segtree	Sky Walking (IOI19_walk)	C++14	0 / 100	43 ms	9080 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{
		return this->height<key.height;
	}
}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});
		for(auto id:disapp[i]){
			auto it=S.lower_bound((st){y[id],id});
			if(it!=S.end()){
				chmin(dp[it->eid],dp[id]+abs(y[id]-it->height));
			}
			if(it!=S.begin()){
				it--;
				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;
}
*/

Compilation message (stderr)

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:15:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define rep(i,n) for(int i=0;i<n;i++)
                  ^
walk.cpp:30:2: note: in expansion of macro 'rep'
  rep(i,m)dp[i]=1e17; dp[m]=0;
  ^~~
walk.cpp:30:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  rep(i,m)dp[i]=1e17; dp[m]=0;
                      ^~

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