Submission #427694

#	Time	Username	Problem	Language	Result	Execution time	Memory
427694		amoo_safar	Sky Walking (IOI19_walk)	C++17	100 / 100	1718 ms	96480 KiB

walk

#include "walk.h"

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;

const int N = 3e5 + 10;

int n, m;
vector<int> x, h, l, r, y;

int seg[N << 2];
int Build(int id, int L, int R){
	if(L + 1 == R) return seg[id] = h[L];
	int mid = (L + R) >> 1;
	return seg[id] = max( Build(id << 1, L, mid), Build(id << 1 | 1, mid, R) );
}
int Seg_Get(int id, int l, int r, int L, int R){
	if(r <= L || R <= l) return -1;
	if(l <= L && R <= r) return seg[id];
	int mid = (L + R) >> 1;
	return max( Seg_Get(id << 1, l, r, L, mid), Seg_Get(id << 1 | 1, l, r, mid, R) );
}
int Get_Max(int l, int r){ // [l, r]
	// cerr << ""
	if(r < l) return -1;
	return Seg_Get(1, l, r + 1, 0, n);
}
vector< pair<ll, ll> > G[N];
void Add_Edge(int a, int b){
	// cerr << "!! " << a << ' ' << b << '\n';
	int ls = max(l[a], l[b]);
	int rs = min(r[a], r[b]);
	if(max(y[a], y[b]) <= Get_Max(ls, rs)){
		G[a].pb({b, abs(y[a] - y[b])});
		G[b].pb({a, abs(y[a] - y[b])});
	}
	// cerr << "!! " << a << ' ' << b << '\n';
}

vector<int> ins[N], dl[N];
void Add(vector<int> sg){
	for(int i = 0; i < N; i++) ins[i].clear(), dl[i].clear();
	for(int i : sg){
		ins[l[i]].pb(i);
		dl[r[i]].pb(i);
	}
	set< pair<int, int> > st; // y id

	for(int i = 0; i < N; i++){
		// cerr << "^^ " << i << '\n';	
		for(auto u : ins[i]){
			// cerr << "&& " << u << ' ' << y[u] << '\n';
			st.insert({y[u], u});
			auto it = st.find({y[u], u});
			if(it != st.begin())
				Add_Edge(it->S, prev(it) -> S);
			if(next(it) != st.end())
				Add_Edge(it->S, next(it) -> S);
		}
		// cerr << "^^ " << i << '\n';
		for(auto u : dl[i]){
			auto it = st.find({y[u], u});
			if(it != st.begin() && next(it) != st.end())
				Add_Edge(next(it) -> S, prev(it) -> S);
			st.erase(it);
		}
	}
}

ll dis[N];
typedef pair<ll, ll> pll;
ll Djik(int src, int des){
	memset(dis, 31, sizeof dis);
	dis[src] = 0;
	set<pll> st;
	st.insert({dis[src], src});
	while(!st.empty()){
		int fr = st.begin() -> S;
		st.erase(st.begin());
		for(auto [adj, w] : G[fr]){
			assert(w >= 0);
			if(dis[adj] > dis[fr] + w){
				st.erase({dis[adj], adj});
				dis[adj] = dis[fr] + w;
				st.insert({dis[adj], adj});
			}
		}
	}
	return dis[des];
}

int Get_Last(int l, int r, int yy){
	for(int i = r; i >= l; i--)
		if(h[i] >= yy)
			return i;
	return l;
}
int Get_First(int l, int r, int yy){
	for(int i = l; i <= r; i++)
		if(h[i] >= yy)
			return i;
	return r;
}


ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int s, int g) {
	if(s > g) swap(s, g);
	x = _x;
	h = _h;
	n = _x.size();

	ll ans = x[g] - x[s];
	
	vector<int> lft, mid, rgt;
	int u, v;
	for(int i = 0; i < (int) _l.size(); i++){
		u = _l[i];
		v = _r[i];
		int a = -1, b = -1, c = -1;
		if(u <= s){
			a = l.size();
			l.pb(u);
			r.pb(min(s, v));
			y.pb(_y[i]);
		}
		if(s <= v && u <= g){
			b = l.size();
			l.pb(max(u, s));
			r.pb(min(g, v));
			y.pb(_y[i]);
		}
		if(g <= v){
			c = l.size();
			l.pb(max(u, g));
			r.pb(v);
			y.pb(_y[i]);
		}
		if(a != -1) lft.pb(a);
		if(b != -1) mid.pb(b);
		if(c != -1) rgt.pb(c);
		if(a != -1 && b != -1){
			G[a].pb({b, 2ll * (x[s] - x[ Get_Last(0, s, _y[i]) ] )});
			G[b].pb({a, 2ll * (x[ Get_First(s, g, _y[i]) ] - x[s])});
		}
		
		if(b != -1 && c != -1){
			G[b].pb({c, 2ll * (x[ Get_First(g, n - 1, _y[i]) ] - x[g]) });
			G[c].pb({b, 2ll * (x[g] - x[ Get_Last(s, g, _y[i]) ])});
		}
	}

	l.pb(s); r.pb(s); y.pb(0);
	l.pb(s); r.pb(s); y.pb(0);

	l.pb(g); r.pb(g); y.pb(0);
	l.pb(g); r.pb(g); y.pb(0);
	
	int src = l.size() - 3;
	int des = l.size() - 1;
	
	mid.pb(src - 1);
	lft.pb(src);
	G[src].pb({src - 1, 0});

	mid.pb(des - 1);
	rgt.pb(des);
	G[des - 1].pb({des, 0});
	m = l.size();
	

	for(int i = 0; i < m; i++)
		assert(l[i] <= r[i]);
	// for(int i = 0; i < m; i++)
	// 	assert(0 <= l[i]);
	// for(int i = 0; i < m; i++)
	// 	assert(r[i] <= n);
	
	// l = _l;
	// r = _r;
	// y = _y;

	// for(int i = 0; i < m; i++) mid.pb(i);
	Build(1, 0, n);
	// debug("A");
	Add(lft);
	// debug("B");
	Add(mid);
	// debug("C");
	Add(rgt);
	// debug("D");

	ans += Djik(src, des);
	ll max_len = 2000000000ll;
	return ans > 1ll * (n + m) * max_len ? -1 : ans;
}

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