Submission #615919

#	Time	Username	Problem	Language	Result	Execution time	Memory
615919		amunduzbaev	Sky Walking (IOI19_walk)	C++17	24 / 100	737 ms	355420 KiB

walk

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

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;
const ll inf = 1e18;
const int N = 1e5 + 5;

struct ST{
	vector<ll> tree;
	vector<ar<int, 2>> c;
	int last;
	void add(){
		tree.push_back(inf);
		c.push_back({});
		last++;
	}
	
	ST(){ add(); }
	
	void umin(int i, ll v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) {
			tree[x] = min(tree[x], v);
			return;
		} int m = (lx + rx) >> 1;
		if(i <= m){
			if(!c[x][0]) c[x][0] = last, add();
			umin(i, v, lx, m, c[x][0]);
		} else {
			if(!c[x][1]) c[x][1] = last, add();
			umin(i, v, m + 1, rx, c[x][1]);
		}
		
		tree[x] = inf;
		if(c[x][0]) tree[x] = min(tree[x], tree[c[x][0]]);
		if(c[x][1]) tree[x] = min(tree[x], tree[c[x][1]]);
	}
	
	ll get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return inf;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		ll res = inf;
		if(c[x][0]) res = min(res, get(l, r, lx, m, c[x][0]));
		if(c[x][1]) res = min(res, get(l, r, m + 1, rx, c[x][1]));
		
		return res;
	}
};

struct ST2{
	ST tree[N << 2];
	
	void umin(int i, int j, ll v, int lx = 0, int rx = N, int x = 1){
		tree[x].umin(j, v);
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		if(i <= m) umin(i, j, v, lx, m, x << 1);
		else umin(i, j, v, m + 1, rx, x << 1 | 1);
	}
	
	ll get(int l, int r, int l_, int r_, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return inf;
		if(lx >= l && rx <= r){
			return tree[x].get(l_, r_);
		}
		
		int m = (lx + rx) >> 1;
		return min(get(l, r, l_, r_, lx, m, x << 1), get(l, r, l_, r_, m + 1, rx, x << 1 | 1));
	}
}add, sub;

vector<ar<int, 2>> edges[N * 11];
ll d[N * 11];

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n = x.size(), q = l.size();
	//~ vector<int> _x(n);
	//~ for(int i=0;i<n;i++){
		//~ _x[i] = x[i];
	//~ }
	
	vector<int> p(q); iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j){
		return y[i] > y[j];
	});
	
	vector<int> P(n); iota(P.begin(), P.end(), 0);
	sort(P.begin(), P.end(), [&](int i, int j){
		return h[i] > h[j];
	});
	
	vector<int> last(n, -1), id(n, -1);
	set<int> ss;
	int j = 0, v = 0;
	for(auto i : p){
		while(j < n && h[P[j]] >= y[i]){
			ss.insert(P[j]);
			j++;
		}
		//~ for(auto x : ss) cout<<x<<" ";
		//~ cout<<"\n";
		//~ cout<<l[i]<<" "<<r[i]<<"\n";
		//~ int k = lower_bound(x.begin(), x.end(), l[i]) - x.begin();
		auto it = ss.lower_bound(l[i]);
		int tmp = -1, X = -1;
		while(it != ss.end() && *it <= r[i]){
			int k = *it;
			//~ cout<<k<<" ";
			if(~tmp){
				edges[v].push_back({tmp, x[k] - X});
				edges[tmp].push_back({v, x[k] - X});
			}
			if(~last[k]){
				edges[v].push_back({last[k], y[id[k]] - y[i]});
				edges[last[k]].push_back({v, y[id[k]] - y[i]});
			}
			last[k] = v, id[k] = i;
			tmp = v, X = x[*it];
			v++;
			it++;
		}
		
		//~ cout<<"\n";
	}
	
	for(int i=0;i<n;i++){
		if(~last[i]){
			edges[v].push_back({last[i], y[id[i]]});
			edges[last[i]].push_back({v, y[id[i]]});
			last[i] = v;
			v++;
		}
	}
	
	//~ last[s], last[g]
	if(last[s] == -1 || last[g] == -1) return -1;
	s = last[s], g = last[g];
	memset(d, 15, sizeof d);
	priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>> > pq;
	d[s] = 0; pq.push({0, s});
	while(!pq.empty()){
		auto [D, u] = pq.top(); pq.pop();
		if(D > d[u]) continue;
		for(auto x : edges[u]){
			if(d[x[0]] > d[u] + x[1]){
				d[x[0]] = d[u] + x[1];
				pq.push({d[x[0]], x[0]});
			}
		}
	}
	
	if(d[g] > inf) return -1;
	return d[g];
}

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