Submission #1197318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197318		HappyCapybara	Sky Walking (IOI19_walk)	C++17	24 / 100	4106 ms	938604 KiB

walk

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

#define ll long long
//#define int long long

int n;
vector<int> h;
vector<vector<int>> st;

bool comp(int a, int b){
	return h[a] < h[b];
}

void build(int node=1, int tl=0, int tr=n-1){
	if (tl == tr){
		st[node] = {tl};
		return;
	}
	int tm = (tl+tr)/2;
	build(node*2, tl, tm);
	build(node*2+1, tm+1, tr);
	st[node] = st[node*2];
	for (int x : st[node*2+1]) st[node].push_back(x);
	sort(st[node].begin(), st[node].end(), comp);
	/*cout << node << " " << tl << " " << tr << endl;
	for (int x : st[node]) cout << x << " ";
	cout << endl;*/
}

vector<int> query(int l, int r, int y, int node=1, int tl=0, int tr=n-1){
	if (l <= tl && tr <= r){
		vector<int> res;
		int lo = -1, hi = st[node].size();
		while (lo < hi-1){
			int mid = (lo+hi)/2;
			if (h[st[node][mid]] >= y) hi = mid;
			else lo = mid;
		}
		for (int i=hi; i<(int)st[node].size(); i++) res.push_back(st[node][i]);
		return res;
	}
	int tm = (tl+tr)/2;
	vector<int> res;
	if (l <= tm) res = query(l, r, y, node*2, tl, tm);
	if (tm+1 <= r){
		vector<int> v = query(l, r, y, node*2+1, tm+1, tr);
		for (int x : v) res.push_back(x);
	}
	return res;
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = x.size();
	int m  = l.size();
	::h = h;
	st.resize(4*n);
	build();
	unordered_map<ll,vector<pair<ll,ll>>> um;
	vector<vector<int>> bh(n);
	bh[s].push_back(0);
	bh[g].push_back(0);
	for (int i=0; i<m; i++){
		vector<int> val = query(l[i], r[i], y[i]);
		sort(val.begin(), val.end());
		/*cout << i << endl;
		for (int x : val) cout << x << " ";
		cout << endl;*/
		for (int j=0; j<(int)val.size(); j++){
			bh[val[j]].push_back(y[i]);
			if (j+1 != (int)val.size()){
				um[((ll)val[j]<<30)+y[i]].push_back({((ll)val[j+1]<<30)+y[i], x[val[j+1]]-x[val[j]]});
				um[((ll)val[j+1]<<30)+y[i]].push_back({((ll)val[j]<<30)+y[i], x[val[j+1]]-x[val[j]]});
			}
		}
	}
	for (int i=0; i<n; i++){
		sort(bh[i].begin(), bh[i].end());
		/*cout << i << endl;
		for (int x : bh[i]) cout << x << " ";
		cout << endl;*/
		for (int j=0; j+1<(int)bh[i].size(); j++){
			um[((ll)i<<30)+bh[i][j]].push_back({((ll)i<<30)+bh[i][j+1], bh[i][j+1]-bh[i][j]});
			um[((ll)i<<30)+bh[i][j+1]].push_back({((ll)i<<30)+bh[i][j], bh[i][j+1]-bh[i][j]});
		}
	}
	priority_queue<pair<ll,ll>> pq;
	pq.push({0, (ll)s<<30});
	unordered_set<ll> seen;
	while (!pq.empty()){
		ll cur = pq.top().second, d = -pq.top().first;
		pq.pop();
		if (seen.find(cur) != seen.end()) continue;
		//cout << (cur>>30) << " " << cur%(1ll<<30) << " " << d << endl;
		seen.insert(cur);
		if (cur == (ll)g<<30) return d;
		for (pair<ll,ll> next : um[cur]) pq.push({-(d+next.second), next.first});
	}
	return -1;
}

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