Submission #590327

#	Time	Username	Problem	Language	Result	Execution time	Memory
590327		Soumya1	Sky Walking (IOI19_walk)	C++17	24 / 100	4089 ms	797232 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
	#include <debug_local.h>
#endif
using namespace std;
template<typename T, class F = function<T(const T&, const T&)>>
struct SparseTable {
  vector<vector<T>> v;
  F f;
  SparseTable() { };
  SparseTable(vector<T> a, F _f) : f(_f) {
    int n = (int) a.size();
    a.resize(n);
    int lg = 32 - __builtin_clz(n);
    v.resize(lg);
    v[0] = a;
    for (int j = 1; j < lg; j++) {
      v[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        v[j][i] = f(v[j - 1][i], v[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
  T query(int l, int r) {
    int lg = 31 - __builtin_clz(r - l + 1);
    return f(v[lg][l], v[lg][r - (1 << lg) + 1]);
  }
};
const int mxN = 5e6 + 5;
vector<pair<int, int>> ad[mxN];
long long 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();
	int m = y.size();
	vector<int> ys[n];
	vector<int> up[n];;
	SparseTable st(h, [&](auto i, auto j) { return max(i, j); });
	for (int i = 0; i < m; i++) {
		up[l[i]].push_back(i);
	}
	for (int i = 0; i < n; i++) {
		ys[i].push_back(0);
		ys[i].push_back(h[i]);
	}
	vector<tuple<int, int, int>> edges;
	for (int i = 0; i < n; i++) {
		for (int j : up[i]) {
			ys[i].push_back(y[j]);
			if (r[j] == i) continue;
			int hi = r[j], lo = i + 1;
			while (lo < hi) {
				int mid = (lo + hi) >> 1;
				if (st.query(i + 1, mid) >= y[j]) hi = mid;
				else lo = mid + 1;
			}
			edges.push_back({i, lo, y[j]});
			up[lo].push_back(j);
		}
		up[i].clear();
	}
	for (int i = 0; i < n; i++) {
		sort(ys[i].begin(), ys[i].end());
		ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
	}
	map<pair<int, int>, int> id;
	int cur = 0;
	map<int, pair<int, int>> who;
	for (int i = 0; i < n; i++) {
		int last = 0;
		for (int yy : ys[i]) {
			who[cur] = {i, yy};
			id[{i, yy}] = cur++;
			ad[id[{i, yy}]].push_back({id[{i, last}], yy - last});
			ad[id[{i, last}]].push_back({id[{i, yy}], yy - last});
			last = yy;
		}
	}
	for (auto [a, b, c] : edges) {
		ad[id[{a, c}]].push_back({id[{b, c}], x[b] - x[a]});
		ad[id[{b, c}]].push_back({id[{a, c}], x[b] - x[a]});
	}
	priority_queue<pair<long long, int>> pq;
	vector<long long> dist(cur, 1e18);
	dist[id[{s, 0}]] = 0;
	pq.push({0, id[{s, 0}]});
	while (!pq.empty()) {
		auto [_, u] = pq.top();
		pq.pop();
		if (dist[u] != -_) continue;
		for (auto [v, w] : ad[u]) {
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				pq.push({-dist[v], v});
			}
		}
	}
	if (dist[id[{g, 0}]] != 1e18) return dist[id[{g, 0}]];
	return -1;
}

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