Submission #1238121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238121		MuhammadSaram	Sky Walking (IOI19_walk)	C++20	24 / 100	674 ms	143512 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int M = 2e6;
const ll inf = 1e18;

vector<pair<int,int>> nei[M];
ll dis[M];

ll dijkstra(int u,int v)
{
	for (int i=0;i<M;i++) dis[i]=inf;
	set<pair<ll,int>> se;
	dis[u]=0;
	se.insert({0,u});
	while (!se.empty())
	{
		pair<ll,int> p=*se.begin();se.erase(p);
		for (auto [i,w]:nei[p.second])
			if (dis[i]>w+p.first)
			{
				se.erase({dis[i],i});
				dis[i]=w+p.first;
				se.insert({dis[i],i});
			}
	}
	return (dis[v]<inf?dis[v]:-1);
}

long long 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();
	vector<pair<int,int>> v1;
	for (int i=0;i<n;i++)
		v1.push_back({h[i],m+i});
	for (int i=0;i<m;i++)
		v1.push_back({y[i],i});
	sort(v1.rbegin(),v1.rend());
	set<int> se;
	vector<pair<int,int>> v[n];
	int id=0;
	for (int i=0;i<n;i++)
		v[i].push_back({0,id++});
	for (auto [i,j]:v1)
	{
		if (j<m)
		{
			auto it=se.lower_bound(l[j]);
			auto it1=se.upper_bound(r[j]);
			int prv=-1,cur,dif;
			while (it!=it1)
			{
				if (v[*it].empty() or v[*it].back().first!=i)
					v[*it].push_back({i,id++});
				int cur=v[*it].back().second;
				if (~prv)
				{
					nei[cur].push_back({prv,x[*it]-dif}),
					nei[prv].push_back({cur,x[*it]-dif});
				}
				prv=cur, dif=x[*it];
				it++;
			}
		}
		else
			se.insert(j-m);
	}
	for (int i=0;i<n;i++)
	{
		sort(v[i].begin(),v[i].end());
		for (int j=1;j<v[i].size();j++)
		{
			int d=v[i][j].first-v[i][j-1].first;
			nei[v[i][j-1].second].push_back({v[i][j].second,d});
			nei[v[i][j].second].push_back({v[i][j-1].second,d});
		}
	}
	return dijkstra(v[s][0].second,v[g][0].second);
}

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