Submission #1051153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051153		Lalic	Sky Walking (IOI19_walk)	C++17	24 / 100	4065 ms	776228 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

ll st[20][100005];
int lg[100005];

void calc(int n){
	lg[0]=lg[1]=0;
	for(int i=2;i<=100000;i++) lg[i]=lg[(i>>1)]+1;
	
	for(int i=1;i<=18;i++)
		for(int j=0;j<n;j++)
			st[i][j]=max(st[i-1][j], st[i-1][min(j+(1<<(i-1)), n)]);
}

ll getMax(int l, int r){
	int pot=lg[r-l+1];
	return max(st[pot][l], st[pot][r-(1<<pot)+1]);
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n=(int)x.size(), m=(int)l.size();
	
	for(int i=0;i<n;i++) st[0][i]=h[i];
	calc(n);
	
	map<pii, ll> dist;
	dist[{s, 0}]=0;
	
	vector<vector<int>> proc(n);
	proc[s].pb(0); proc[g].pb(0);
	
	map<pii, vector<pii>> adj;
	for(int i=0;i<m;i++){
		int curr=l[i];
		while(curr!=r[i]){
			int low=curr+1, high=r[i]-1, best=r[i];
			
			while(low<=high){
				int mid=(low+high)>>1;
				if(getMax(curr+1, mid)>=y[i]){
					best=mid;
					high=mid-1;
				}
				else low=mid+1;
			}
			
			proc[curr].pb(y[i]);
			proc[best].pb(y[i]);
			
			//~ cout << "added: " << curr << " -> " << best << " at " << y[i] << "\n";
			adj[{curr, y[i]}].pb({best, y[i]});
			adj[{best, y[i]}].pb({curr, y[i]});
			curr=best;
		}
	}
	
	for(int i=0;i<n;i++) sort(all(proc[i]));
	
	for(int i=0;i<n;i++){
		for(int j=1;j<(int)proc[i].size();j++)
			adj[{i, proc[i][j-1]}].pb({i, proc[i][j]}), adj[{i, proc[i][j]}].pb({i, proc[i][j-1]});
	}
	
	priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<>> pq;
	pq.push({0ll, {s, 0}});
	while(!pq.empty()){
		ll d=pq.top().fi;
		int id=pq.top().se.fi, alt=pq.top().se.se;
		pq.pop();
		
		if(dist[{id, alt}]<d) continue;
		
		for(auto u : adj[{id, alt}]){
			if(dist.find(u)==dist.end() || dist[u]>d+(ll)(abs(u.se-alt)+abs(x[u.fi]-x[id]))){
				dist[u]=d+(ll)(abs(u.se-alt)+abs(x[u.fi]-x[id]));
				pq.push({dist[u], u});
			}
		}
	}
	
	if(dist.find({g, 0})==dist.end()) return -1;
	return dist[{g, 0}];
}

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