Submission #1048401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048401		Malix	Sky Walking (IOI19_walk)	C++14	24 / 100	2159 ms	673620 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
 
ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

int n,m;
vi st;
vi arr;

void build(int x,int l,int r){
	if(l==r){
		st[x]=arr[l];
		return;
	}
	int m=(l+r)/2;
	build(2*x,l,m);
	build(2*x+1,m+1,r);
	st[x]=max(st[2*x],st[2*x+1]);
}

int mx(int x,int l,int r,int a,int b){
	if(a>b)return 0;
	if(l==a&&r==b)return st[x];
	int m=(l+r)/2;
	return max(mx(2*x,l,m,a,min(b,m)),mx(2*x+1,m+1,r,max(a,m+1),b));
}

int solve(int h,int l,int r){
	if(l==r)return l;
	int m=(l+r)/2;
	int k=mx(1,0,n-1,l,m);
	if(k>=h)return solve(h,l,m);
	else return solve(h,m+1,r);
}

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	n=x.size();m=l.size();
	st.resize(4*n);
	arr=h;
	build(1,0,n-1);
	map<int,pi> mp;
	int k=0;
	vector<pii> a(2e6);
	vector<set<pi>> b(n);
	REP(i,0,m){
		int p=l[i];
		mp[k]={l[i],y[i]};
		b[l[i]].insert({y[i],k});
		k++;
		while(p<r[i]){
			int t=solve(y[i],p+1,r[i]);
			mp[k]={t,y[i]};
			b[t].insert({y[i],k});
			int dis=x[t]-x[p];
			a[k].PB({k-1,dis});
			a[k-1].PB({k,dis});
			k++;
			p=t;
		}
	}
	int spos=s,epos=g;
	REP(i,0,n){
		if(i==s)spos=k;
		if(i==g)epos=k;
		mp[k]={i,0};
		int c=0,d=k;
		for(auto u:b[i]){
			a[d].PB({u.S,u.F-c});
			a[u.S].PB({d,u.F-c});
			c=u.F;d=u.S;
		}
		k++;
	}
	vector<ll> dist(k+1,INF);
	priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
	pq.push({0,spos});dist[spos]=0;
	while(!pq.empty()){
		ll distance=pq.top().F;
		int node=pq.top().S;
		pq.pop();
		if(dist[node]<distance)continue;
		for(auto u:a[node]){
			if(dist[u.F]<=distance+u.S)continue;
			dist[u.F]=distance+u.S;
			pq.push({dist[u.F],u.F});
		}
	}
	if(dist[epos]==INF)return -1;
	return dist[epos];
}

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