Submission #1038943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038943		AmirAli_H1	Sky Walking (IOI19_walk)	C++17	24 / 100	599 ms	245072 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 + 4;
const int maxs = 1e5 + 4;
const int maxlg = 20;
const ll oo = 1e18 + 4;

int sz, n, m;
vector<pll> adj[maxn];
vector<int> A[maxn], ls; pll val[maxn];
ll dis[maxn]; bool mark[maxn];
pii rmq[maxs][maxlg];
priority_queue<pll> qu;

void addE(int i, int j) {
	ll w = abs(val[i].F - val[j].F) + abs(val[i].S - val[j].S);
	adj[i].pb(Mp(j, w)); adj[j].pb(Mp(i, w));
}

int get_max(int l, int r) {
	int j = __lg(r - l);
	return max(rmq[l][j], rmq[r - (1 << j)][j]).S;
}

void get_val(int l, int r, ll x) {
	if (r - l <= 0) return ;
	int j = get_max(l, r);
	if (rmq[j][0].F < x) return ;
	ls.pb(j);
	get_val(l, j, x); get_val(j + 1, r, x);
}

bool cmp(int i, int j) {
	return (val[i].S < val[j].S);
}

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 min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	sz = 0; n = len(h); m = len(y);
	int v1 = sz++;
	val[v1] = Mp(x[s], 0); A[s].pb(v1);
	int v2 = sz++;
	val[v2] = Mp(x[g], 0); A[g].pb(v2);
	
	for (int i = n - 1; i >= 0; i--) {
		rmq[i][0] = Mp(h[i], 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]);
		}
	}
	
	for (int i = 0; i < m; i++) {
		ls.clear();
		get_val(l[i], r[i] + 1, y[i]);
		sort(all(ls));
		
		int vx = -1, ux = -1;
		for (int j : ls) {
			vx = sz++;
			val[vx] = Mp(x[j], y[i]); A[j].pb(vx);
			if (ux != -1) addE(ux, vx);
			ux = vx;
		}
	}
	
	for (int i = 0; i < n; i++) {
		sort(all(A[i]), cmp);
		for (int j = 1; j < len(A[i]); j++) {
			addE(A[i][j - 1], A[i][j]);
		}
	}
	
	dij(v1);
	if (dis[v2] == oo) return -1;
	else return dis[v2];
}

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