Submission #303317

#	Time	Username	Problem	Language	Result	Execution time	Memory
303317		ainta	Sky Walking (IOI19_walk)	C++17	15 / 100	223 ms	23020 KiB

walk

#include "walk.h"
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
#define N_ 101000
#define SZ 131072

vector<ll>X, Y;
struct Seg{
	int ed, y;
};
vector<Seg>LeftSeg[N_], RightSeg[N_];
int n, m, H[N_];
ll INF = 1e18;

struct Tree{
	ll IT[SZ+SZ];
	void init(){
		for(int i=0;i<SZ+SZ;i++)IT[i]=INF;
	}
	void Put(int y, ll d){
		y+=SZ;
		IT[y] = d;
		while(y!=1){
			y>>=1;
			IT[y]=min(IT[y*2],IT[y*2+1]);
		}
	}
	ll Min(int b, int e){
		ll r=INF;
		b+=SZ,e+=SZ;
		while(b<=e){
			r=min(r,min(IT[b],IT[e]));
			b=(b+1)>>1,e=(e-1)>>1;
		}
		return r;
	}
}T1, T2;

ll U[N_];

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) {
	int i;
	for(auto &t : x)X.push_back(t);
	vector<pii>ordY;
	n = x.size();
	m = l.size();
	for(i=0;i<m;i++){
		ordY.push_back({y[i],i});
	}
	sort(ordY.begin(),ordY.end());
	for(i=0;i<m;i++){
		Y.push_back(ordY[i].first);
		int t = ordY[i].second;
		RightSeg[l[t]].push_back({r[t], i});
		LeftSeg[r[t]].push_back({l[t], i});
	}
	for(i=0;i<n;i++){
		H[i]=lower_bound(Y.begin(),Y.end(),h[i]+1)-Y.begin();
		H[i]--;
	}
	if(s>g)swap(s,g);

	T1.init();
	T2.init();
	vector<pll>Save;
	for(i=0;i<=s;i++){
		for(auto &t : RightSeg[i]){
			if(t.ed >= s && t.y <= H[s]){
				T1.Put(t.y, Y[t.y] + X[i] - Y[t.y]);
				T2.Put(t.y, Y[t.y] + X[i] + Y[t.y]);
				Save.push_back({t.y, Y[t.y]});
			}
		}
	}
	for(i=s-1;i>=0;i--){
		for(auto &t: RightSeg[i+1]){
			T1.Put(t.y, INF);
			T2.Put(t.y, INF);
		}
		for(auto &t : LeftSeg[i]){
			ll d = min(T1.Min(0,t.y) - X[i] + Y[t.y], T2.Min(t.y,H[i]) - X[i] - Y[t.y]);
			T1.Put(t.y, d + X[i] - Y[t.y]);
			T2.Put(t.y, d + X[i] + Y[t.y]);
		}
		for(auto &t : RightSeg[i]){
			if(t.ed > s && t.y > H[s]){
				ll d = min(T1.Min(0,t.y) - X[i] + Y[t.y], T2.Min(t.y,H[i]) - X[i] - Y[t.y]);
				Save.push_back({t.y, d + X[s] - X[i]});
			}
		}
	}
	T1.init();
	T2.init();
	for(auto &t : Save){
		T1.Put(t.first, t.second - X[s] - Y[t.first]);
		T2.Put(t.first, t.second - X[s] + Y[t.first]);
	}
	ll res = 1e18;
	for(i=s+1;i<=g;i++){
		for(auto &t : LeftSeg[i-1]){
			T1.Put(t.y, INF);
			T2.Put(t.y, INF);
		}
		if(i==g){
			res = min(res, T2.Min(0,H[i]) + X[i]);
		}
		for(auto &t : RightSeg[i]){
			ll d = min(T1.Min(0,t.y) + X[i] + Y[t.y], T2.Min(t.y,H[i]) + X[i] - Y[t.y]);
			T1.Put(t.y, d - X[i] - Y[t.y]);
			T2.Put(t.y, d - X[i] + Y[t.y]);
		}
	}
	for(i=0;i<m;i++){
		U[i] = T1.IT[SZ+i] + X[g] + Y[i];
	}
	T1.init();T2.init();
	for(i=0;i<=g;i++){
		for(auto &t : RightSeg[i]){
			if(t.ed > g && t.y <= H[g]){
				T1.Put(t.y, Y[t.y] - X[g] - Y[t.y]);
				T2.Put(t.y, Y[t.y] - X[g] + Y[t.y]);
			}
		}
	}
	int pv = H[g]+1;
	for(i=g+1;i<n;i++){
		for(auto &t : LeftSeg[i-1]){
			T1.Put(t.y, INF);
			T2.Put(t.y, INF);
		}
		while(pv <= H[i]){
			ll d = min(T1.Min(0,pv) + X[i] + Y[pv], T2.Min(pv,H[i]) + X[i] - Y[pv]);
			res = min(res, d + X[i]-X[g] + U[pv]);
			pv++;
		}
		for(auto &t : RightSeg[i]){
			ll d = min(T1.Min(0,t.y) + X[i] + Y[t.y], T2.Min(t.y,H[i]) + X[i] - Y[t.y]);
			T1.Put(t.y, d - X[i] - Y[t.y]);
			T2.Put(t.y, d - X[i] + Y[t.y]);
		}
	}
	if(res>1e16)res=-1;
	return res;
}

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