Submission #1228715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228715		AmirAli_H1	Sky Walking (IOI19_walk)	C++17	57 / 100	1773 ms	582092 KiB

walk

// In the name of Allah

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

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

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 7;
const ll oo = 1e18 + 4;
const int maxlg = 20;

int n, m, sz, ux, vx;
pii A[maxn]; pair<pii, int> Q[maxn];
vector<pll> adj[maxn]; ll dis[maxn];
vector<int> arr, ls1[maxn], ls2[maxn];
set<int> st; int cnt[maxn];
priority_queue<pll> qu; int mark[maxn];
vector<int> ls[maxn]; int ind[maxn];
pll rmq[maxn][maxlg];

int GI(int x) {
	return lower_bound(all(arr), x) - arr.begin();
}

ll calx(int j) {
	ll res = oo;
	auto it = st.lower_bound(j);
	if (it != st.end()) {
		int w = (*it);
		res = min(res, dis[w] + (arr[w] - arr[j]));
	}
	if (it != st.begin()) {
		it--; int w = (*it);
		res = min(res, dis[w] + (arr[j] - arr[w]));
	}
	return res;
}

ll solvex() {
	arr.pb(0);
	for (int i = 0; i < m; i++) {
		int l = Q[i].F.F, r = Q[i].F.S; int x = Q[i].S;
		arr.pb(x);
	}
	sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());
	for (int i = 0; i < m; i++) {
		int l = Q[i].F.F, r = Q[i].F.S; int x = Q[i].S;
		int j = GI(x); ls1[l].pb(j); ls2[r].pb(j);
	}
	fill(dis, dis + len(arr), oo); fill(cnt, cnt + len(arr), 0);
	for (int i = 0; i < n - 1; i++) {
		for (int j : ls1[i]) {
			cnt[j]++;
			if (cnt[j] == 1) {
				if (i == 0) dis[j] = arr[j];
				else dis[j] = calx(j);
				st.insert(j);
			}
		}
		for (int j : ls2[i]) {
			cnt[j]--;
			if (cnt[j] == 0) {
				dis[j] = oo; st.erase(j);
			}
		}
	}
	ll res = calx(0) + (A[n - 1].F - A[0].F);
	if (res >= oo) return -1;
	return res;
}

int GIx(int u, int x) {
	int j = lower_bound(all(ls[u]), x) - ls[u].begin();
	return ind[u] + j;
}

pll get_max(int l, int r) {
	if (r - l <= 0) return Mp(-oo, -1);
	int j = __lg(r - l);
	return max(rmq[l][j], rmq[r - (1 << j)][j]);
}

void addE(int u, int v, ll w) {
	adj[u].pb(Mp(v, w)); adj[v].pb(Mp(u, w));
}

void addx(int l, int r, int x) {
	if (r - l <= 1) return ;
	auto f = get_max(l + 1, r - 1);
	if (f.F >= x) {
		addx(l, f.S + 1, x); addx(f.S, r, x);
	}
	else {
		ls[l].pb(x); ls[r - 1].pb(x);
	}
}

void adde(int l, int r, int x) {
	if (r - l <= 1) return ;
	auto f = get_max(l + 1, r - 1);
	if (f.F >= x) {
		adde(l, f.S + 1, x); adde(f.S, r, x);
	}
	else {
		addE(GIx(l, x), GIx(r - 1, x), (A[r - 1].F - A[l].F));
	}
}

void dij(int v) {
	fill(dis, dis + sz, oo); fill(mark, mark + sz, 0);
	dis[v] = 0; qu.push(Mp(-dis[v], v));
	while (!qu.empty()) {
		int v = qu.top().S; qu.pop();
		if (mark[v]) continue;
		mark[v] = 1;
		for (auto f : adj[v]) {
			int u = f.F; ll w = f.S;
			if (dis[v] + w < dis[u]) {
				dis[u] = dis[v] + w;
				qu.push(Mp(-dis[u], u));
			}
		}
	}
}

ll solve() {
	for (int i = n - 1; i >= 0; i--) {
		rmq[i][0] = Mp(A[i].S, i);
		for (int j = 1; j < maxlg; j++) {
			if (i + (1 << j) - 1 >= n) break;
			rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
		}
	}
	ls[ux].pb(0); ls[vx].pb(0);
	for (int i = 0; i < m; i++) {
		int l = Q[i].F.F, r = Q[i].F.S; int x = Q[i].S;
		addx(l, r + 1, x);
	}
	sz = 0;
	for (int i = 0; i < n; i++) {
		sort(all(ls[i])); ls[i].resize(unique(all(ls[i])) - ls[i].begin());
		if (i - 1 >= 0) ind[i] = ind[i - 1] + len(ls[i - 1]);
		else ind[i] = 0;
		for (int j = 1; j < len(ls[i]); j++) {
			addE(ind[i] + (j - 1), ind[i] + j, ls[i][j] - ls[i][j - 1]);
		}
		sz += len(ls[i]);
	}
	for (int i = 0; i < m; i++) {
		int l = Q[i].F.F, r = Q[i].F.S; int x = Q[i].S;
		adde(l, r + 1, x);
	}
	int u = GIx(ux, 0), v = GIx(vx, 0); dij(u);
	if (dis[v] >= oo) return -1;
	return dis[v];
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = len(x); m = len(l); ux = s; vx = g;
	if (ux > vx) swap(ux, vx);
	for (int i = 0; i < n; i++) {
		A[i] = Mp(x[i], h[i]);
	}
	for (int i = 0; i < m; i++) {
		Q[i] = Mp(Mp(l[i], r[i]), y[i]);
	}
	if (ux == 0 && vx == n - 1) return solvex();
	else return solve();
}

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