Submission #602990

#	Time	Username	Problem	Language	Result	Execution time	Memory
602990		Koosha_mv	Sky Walking (IOI19_walk)	C++14	33 / 100	225 ms	27836 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=1e5+99;
const ll inf=1e16;

int n,m;
ll dist[N],pos[N],seg[2][N<<2];
vector<int> ad[N],dl[N];
vector<pair<int,int>> vec;

void change(int x,ll val,int s){
	x+=m;
	seg[s][x]=val;
	for(;x>1;x>>=1){
		seg[s][x>>1]=min(seg[s][x],seg[s][x^1]);
	}
}
ll get(int l,int r,int s){
	ll ans=inf;
	for(l+=m,r+=m;l<r;l>>=1,r>>=1){
		if(l&1){
			minm(ans,seg[s][l++]);
		}
		if(r&1){
			minm(ans,seg[s][--r]);
		}
	}
	return ans;
}

ll min_distance(vector<int> a,vector<int> h,vector<int> l,vector<int> r,vector<int> y,int s,int g) {
	n=a.size();
	y.pb(0);
	l.pb(n-1);
	r.pb(n-1);
	m=l.size();

	f(i,0,m){
		ad[l[i]].pb(i);
		dl[r[i]].pb(i);
		vec.pb({y[i],i});
	}
	
	sort(all(vec));
	f(i,0,int(vec.size())) pos[vec[i].S]=i;
	f(s,0,2) f(i,0,N<<2) seg[s][i]=inf;
	f(i,0,n){
		for(auto x : ad[i]){
			dist[x]=min(y[x]+get(0,pos[x],0),get(pos[x],m,1)-y[x]);
			if(l[x]==0) dist[x]=y[x];
			//cout<<x<<" -> "<<dist[x]<<endl;
			change(pos[x],dist[x]-y[x],0);
			change(pos[x],dist[x]+y[x],1);
		}	
		for(auto x : dl[i]){
			change(pos[x],inf,0);
			change(pos[x],inf,1);
		}
	}
	if(dist[m-1]>=inf){
		return -1;
	}
	else{
		return a[n-1]-a[0]+dist[m-1];
	}
}
/*
5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4

0, 4, 5, 6, 9],
[6, 6, 6, 6, 6],
[3, 1, 0],
[4, 3, 2],
[1, 3, 6],
0, 4)
*/

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