Submission #615991

#	Time	Username	Problem	Language	Result	Execution time	Memory
615991		amunduzbaev	Sky Walking (IOI19_walk)	C++17	57 / 100	3983 ms	883624 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 = 2e18;
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 = 0){
		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 = 0){
		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];

#define sow cout<<"here"<<endl;

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();
	if(s == 0 && g == n - 1){
		int n = x.size(), q = l.size();
		vector<int> p(q); iota(p.begin(), p.end(), 0);
		sort(p.begin(), p.end(), [&](int i, int j){
			return r[i] < r[j];
		});
		
		vector<int> tot;
		vector<ll> dp(q, inf);
		for(int i=0;i<q;i++){
			tot.push_back(y[i]);
		}
		
		sort(tot.begin(), tot.end());
		tot.erase(unique(tot.begin(), tot.end()), tot.end());
		ll res = inf;
		sub.umin(0, 0, 0);
		add.umin(0, 0, 0);
		for(auto i : p){
			int j = lower_bound(tot.begin(), tot.end(), y[i]) - tot.begin() + 1;
			dp[i] = min(dp[i], sub.get(l[i], r[i], 0, j) + y[i]);
			dp[i] = min(dp[i], add.get(l[i], r[i], j, q) - y[i]);
			sub.umin(r[i], j, dp[i] - y[i]);
			add.umin(r[i], j, dp[i] + y[i]);
			if(r[i] == n - 1) res = min(res, dp[i] + y[i]);
		}
		
		res += (x[n - 1] - x[0]);
		if(res < 1e18){
			return res;
		} else {
			return -1;
		}
	} else {
		int q = l.size();
		
		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, 31, 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: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43