Submission #1039000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039000		parsadox2	Sky Walking (IOI19_walk)	C++17	33 / 100	152 ms	25396 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int N = 1e5 + 10;
const long long inf = 1e18;

int n , m , a[N] , pos[N];
long long dis[N];
vector <int> comp , st[N] , fn[N];

struct bridge{
	int l , r , y;
};
vector <bridge> vec;

bool cmp(bridge aa , bridge bb)
{
	return aa.l < bb.l;
}

struct SEG{
	long long mn[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = m)
	{
		mn[node] = inf;
		if(nr - nl == 1)
			return;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);
		Build(rc , mid , nr);
	}
	void Set(int id , long long val , int node = 1 , int nl = 0 , int nr = m)
	{
		if(nr - nl == 1)
		{
			mn[node] = val;
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		if(id < mid)
			Set(id , val , lc , nl , mid);
		else
			Set(id , val , rc , mid , nr);
		mn[node] = min(mn[lc] , mn[rc]);
	}
	long long Get(int l , int r , int node = 1 , int nl = 0 , int nr = m)
	{
		if(r <= nl || nr <= l)
			return inf;
		if(l <= nl && nr <= r)
			return mn[node];
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		return min(Get(l , r , lc , nl , mid) , Get(l , r , rc , mid , nr));
	}
} seg[2];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = x.size();
	m = l.size();
	for(int i = 0 ; i < n ; i++)
	{
		a[i] = h[i];
		pos[i] = x[i];
	}
	for(int i = 0 ; i < m ; i++)
		comp.push_back(y[i]);
	seg[0].Build();
	seg[1].Build();
	sort(comp.begin() , comp.end());
	comp.resize(unique(comp.begin() , comp.end()) - comp.begin());
	for(int i = 0 ; i < m ; i++)
	{
		y[i] = lower_bound(comp.begin() , comp.end() , y[i]) - comp.begin();
		st[l[i]].push_back(i);
		fn[r[i]].push_back(i);
		//cout << i << " : " << l[i] << " " << r[i] << " " << y[i] << " " << comp[y[i]] << endl;
	}
	for(auto u : st[0])
	{
		dis[u] = comp[y[u]];
		seg[0].Set(y[u] , dis[u] - comp[y[u]]);
		seg[1].Set(y[u] , dis[u] + comp[y[u]]);
		//cout << u << " : " << dis[u] << endl;
	}
	for(int i = 1 ; i < n ; i++)
	{
		for(auto u : st[i])
		{
			//cout << u << " WTF " << seg[0].Get(0 , y[u]) << " " << seg[1].Get(y[u] , m) << endl;
			dis[u] = min(seg[0].Get(0 , y[u]) + comp[y[u]] , seg[1].Get(y[u] , m) - comp[y[u]]);
		}
		for(auto u : fn[i])
		{
			seg[0].Set(y[u] , inf);
			seg[1].Set(y[u] , inf);
		}
		for(auto u : st[i])
		{
			//cout << u << " : " << dis[u] << endl;
			seg[0].Set(y[u] , dis[u] - comp[y[u]]);
			seg[1].Set(y[u] , dis[u] + comp[y[u]]);
		}
	}
	long long res = inf;
	for(auto u : fn[n - 1])
		res = min(res , dis[u] + comp[y[u]]);
	res += (pos[n - 1] - pos[0]);
	if(res >= inf)
		res = -1;
	return res;
}

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