Submission #171534

#	Time	Username	Problem	Language	Result	Execution time	Memory
171534		youngyojun	Sky Walking (IOI19_walk)	C++17	100 / 100	2073 ms	134904 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define fi first
#define se second
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
inline void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }

const int MAXN = 100055;
const int MAXM = 100055;
const int MAXK = 2000055;

struct EVT {
	EVT(int type, pii p)
		: type(type), p(p) {}
	int type;
	pii p;

	bool operator < (const EVT &t) const {
		if(p.fi != t.p.fi) return p.fi < t.p.fi;
		return type < t.type;
	}
};

vector<int> G[MAXK];
ll dp[MAXK];

vector<pii> PV;

int A[MAXN], B[MAXN];
int C[MAXM], D[MAXM], E[MAXM];

int N, M, K, Si, Ei;

ll solve() {
	{
		vector<pii> OV;
		for(int i = N; i--;) OV.eb(-B[i], -(i+1));
		for(int i = M; i--;) OV.eb(-E[i], i+1);
		sorv(OV);

		auto f = [&](int x) {
			set<int> PQ;
			for(auto &ev : OV) {
				int idx = ev.se;
				if(idx < 0) {
					idx = -idx-1;
					PQ.insert(idx);
				} else {
					idx--;
					if(D[idx] <= x) {
						auto it = PQ.find(D[idx]);
						PV.eb(A[*it], E[idx]);
						PV.eb(A[*prev(it)], E[idx]);
					} else if(x <= C[idx]) {
						auto it = PQ.find(C[idx]);
						PV.eb(A[*it], E[idx]);
						PV.eb(A[*next(it)], E[idx]);
					} else {
						auto it = PQ.upper_bound(x-1);
						if(PQ.begin() != it) {
							it--;
							if(C[idx] <= *it && *it <= D[idx])
								PV.eb(A[*it], E[idx]);
						}
						it = PQ.upper_bound(x);
						if(PQ.end() != it && C[idx] <= *it && *it <= D[idx])
							PV.eb(A[*it], E[idx]);
					}
				}
			}
		};
		f(Si); f(Ei);
	}

	{
		vector<EVT> EV;
		for(int i = M; i--;) {
			EV.eb(0, pii(A[C[i]], E[i]));
			EV.eb(2, pii(A[D[i]], E[i]));
		}
		for(auto &v : PV) EV.eb(1, v);
		sorv(EV);

		multiset<int> PQ;
		for(auto &ev : EV) {
			if(!ev.type) PQ.insert(ev.p.se);
			else if(1 == ev.type) {
				auto it = PQ.upper_bound(ev.p.se);
				if(PQ.end() != it) PV.eb(ev.p.fi, *it);
				if(PQ.begin() != it && *prev(it) == ev.p.se) it--;
				if(PQ.begin() != it) PV.eb(ev.p.fi, *prev(it));
			} else PQ.erase(PQ.find(ev.p.se));
		}
	}

	PV.eb(A[Si], 0); PV.eb(A[Ei], 0);
	for(int i = M; i--;) {
		if(C[i] <= Si && Si <= D[i] && E[i] <= B[Si]) PV.eb(A[Si], E[i]);
		if(C[i] <= Ei && Ei <= D[i] && E[i] <= B[Ei]) PV.eb(A[Ei], E[i]);
	}

	sorv(PV); univ(PV);
	{
		vector<pii> V; K = sz(PV);
		for(int i = 0, s = 0, e; i < N; i++, s = e) {
			for(e = s; e < K && PV[e].fi == A[i]; e++);
			for(int j = s; j < e; j++)
				if(PV[j].se <= B[i]) V.eb(PV[j]);
		}
		swap(PV, V);
	}
	K = sz(PV);
	fill(dp, dp+MAXK, INFLL);
	{ int x = A[Si]; for(Si = 0; PV[Si].fi != x || PV[Si].se; Si++); }
	{ int x = A[Ei]; for(Ei = 0; PV[Ei].fi != x || PV[Ei].se; Ei++); }

	for(int i = 1; i < K; i++)
		if(PV[i-1].fi == PV[i].fi) fg(G, i-1, i);

	{
		auto cmp = [&](const pii &a, const pii &b) {
			if(a.se != b.se) return a.se < b.se;
			return a.fi < b.fi;
		};
		vector<pair<pii, int>> _PV(K);
		for(int i = K; i--;) _PV[i] = {PV[i], i};
		sort(allv(_PV), [&](const pair<pii, int> &a, const pair<pii, int> &b) { return cmp(a.fi, b.fi); });

		vector<int> OV;
		for(int i = M; i--;) OV.eb(i);
		sort(allv(OV), [&](int a, int b) { return cmp({A[C[a]], E[a]}, {A[C[b]], E[b]}); });

		for(int i = 0, j = 0, idx; i < M; i++) {
			idx = OV[i];
			for(; j < K && cmp(_PV[j].fi, {A[C[idx]], E[idx]}); j++);
			for(j++; j < K && _PV[j].fi.se == E[idx] && _PV[j].fi.fi <= A[D[idx]]; j++) fg(G, _PV[j-1].se, _PV[j].se);
			if(j) j--;
		}
	}
	
	{
		priority_queue<pli, vector<pli>, greater<pli>> PQ;
		dp[Si] = 0; PQ.emplace(0, Si);
		for(ll dst; !PQ.empty();) {
			int idx; tie(dst, idx) = PQ.top(); PQ.pop();
			if(dp[idx] < dst) continue;
			for(int v : G[idx]) {
				ll ndst = dst + abs(PV[idx].fi - PV[v].fi) + abs(PV[idx].se - PV[v].se);
				if(dp[v] <= ndst) continue;
				dp[v] = ndst;
				PQ.emplace(ndst, v);
			}
		}
	}
	return dp[Ei] >= INFLL ? -1 : dp[Ei];
}

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 = sz(x); ::M = sz(l);
	for(int i = 0; i < ::N; i++) {
		::A[i] = x[i];
		::B[i] = h[i];
	}
	for(int i = 0; i < ::M; i++) {
		::C[i] = l[i];
		::D[i] = r[i];
		::E[i] = y[i];
	}
	::Si = s; ::Ei = g;
	return solve();
}

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