Submission #1243266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243266		Zbyszek99	Sky Walking (IOI19_walk)	C++20	100 / 100	1540 ms	191412 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct point
{
	int y,ind,type;
};

vector<point> points_on[100001];
vector<pll> graph[1000001];
vector<pii> eq_y[100001];
vector<pii> eq_x[100001];
pii poz[1000001];
ll dist[1000001];

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) 
{
	set<pii> points_graph;
	int n = siz(x);
	int m = siz(l);
	vi s_left(n);
	vi s_right(n);
	vi g_left(n);
	vi g_right(n);
	int sl = 0;
	int sr = 0;
	int gl = 0;
	int gr = 0;
	rep(i,n)
	{
		if(i >= s) sr = max(sr,h[i]);
		if(i >= g) gr = max(gr,h[i]);
		g_right[i] = gr;
		s_right[i] = sr;	
	}
	for(int i = n-1; i >= 0; i--)
	{
		if(i <= s) sl = max(sl,h[i]);
		if(i <= g) gl = max(gl,h[i]);
		s_left[i] = sl;
		g_left[i] = gl;
	}
	rep(i,m)
	{
		if(l[i] <= s && r[i] >= s)
		{
			if(h[s] >= y[i]) points_on[s].pb({y[i],i,2});
			int l2 = s;
			int r2 = r[i];
			int ans = 0;
			while(l2 <= r2)
			{
				int mid = (l2+r2)/2;
				if(s_right[mid] >= y[i])
				{
					ans = mid;
					r2 = mid-1;
				}
				else
				{
					l2 = mid+1;
				}
			}
			points_on[ans].pb({y[i],i,2});
			l2 = l[i];
			r2 = s;
			while(l2 <= r2)
			{
				int mid = (l2+r2)/2;
				if(s_left[mid] >= y[i])
				{
					ans = mid;
					l2 = mid+1;
				}
				else
				{
					r2 = mid-1;
				}
			}
			points_on[ans].pb({y[i],i,2});
		}
		if(l[i] <= g && r[i] >= g)
		{
			if(h[g] >= y[i]) points_on[g].pb({y[i],i,2});
			int l2 = g;
			int r2 = r[i];
			int ans = 0;
			while(l2 <= r2)
			{
				int mid = (l2+r2)/2;
				if(g_right[mid] >= y[i])
				{
					ans = mid;
					r2 = mid-1;
				}
				else
				{
					l2 = mid+1;
				}
			}
			points_on[ans].pb({y[i],i,2});
			l2 = l[i];
			r2 = g;
			while(l2 <= r2)
			{
				int mid = (l2+r2)/2;
				if(g_left[mid] >= y[i])
				{
					ans = mid;
					l2 = mid+1;
				}
				else
				{
					r2 = mid-1;
				}
			}
			points_on[ans].pb({y[i],i,2});	
		}
	}
	rep(i,m)
	{
		points_on[l[i]].pb({y[i],i,1});
		points_on[r[i]].pb({y[i],i,-1});
	}
	set<pii> cur_on;
	rep(i,n)
	{
		forall(it,points_on[i]) if(it.type == 1) cur_on.insert({it.y,it.ind});
		forall(it,points_on[i])
		{
			points_graph.insert({i,it.ind});
			auto nxt = cur_on.upper_bound({it.y,it.ind});
			if(nxt != cur_on.end() && y[(*nxt).ss] <= h[i])
			{
				points_graph.insert({i,(*nxt).ss});
			}
			nxt = cur_on.lower_bound({it.y,it.ind});
			if(nxt != cur_on.begin())
			{
				nxt--;
				points_graph.insert({i,(*nxt).ss});
			}
		}
		forall(it,points_on[i]) if(it.type == -1) cur_on.erase(cur_on.find({it.y,it.ind}));
	}
	int cur = 0;
	forall(it,points_graph)
	{
		poz[cur] = it;
		eq_y[it.ss].pb({it.ff,cur});
		eq_x[it.ff].pb({y[it.ss],cur});
		cur++;
	}	
	rep(i,n)
	{
		sort(all(eq_x[i]));
		pii pop = {-1,-1};
		forall(it,eq_x[i])
		{
			if(pop.ff != -1)
			{
				graph[pop.ss].pb({it.ss,abs(it.ff-pop.ff)});
				graph[it.ss].pb({pop.ss,abs(it.ff-pop.ff)});
			}
			pop = it;
		}
	}
	rep(i,m)
	{
		sort(all(eq_y[i]));
		pii pop = {-1,-1};
		forall(it,eq_y[i])
		{
			if(pop.ff != -1)
			{
				graph[pop.ss].pb({it.ss,abs(x[it.ff]-x[pop.ff])});
				graph[it.ss].pb({pop.ss,abs(x[it.ff]-x[pop.ff])});
			}
			pop = it;
		}
	}
	rep(i,cur) dist[i] = 1e18;
	priority_queue<pll,vector<pll>,greater<pll>> pq;
	rep(i,cur)
	{
		if(poz[i].ff == s) pq.push({y[poz[i].ss],i});
	}
	while(!pq.empty())
	{
		pll t = pq.top();
		pq.pop();
		if(t.ff >= dist[t.ss]) continue;
		dist[t.ss] = t.ff;
		forall(it,graph[t.ss]) pq.push({t.ff+it.ss,it.ff});
	}
	ll ans = 1e18;
	rep(i,cur) if(poz[i].ff == g) ans = min(ans,dist[i]+y[poz[i].ss]);
	if(ans == 1e18) ans = -1;
	return ans;
}

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