oj.uz

Submission #590327

# Submission time Handle Problem Language Result Execution time Memory
590327 2022-07-05T20:38:40 Z Soumya1 Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 797232 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 117708 KB Output is correct
2 Correct 53 ms 117704 KB Output is correct
3 Correct 54 ms 117644 KB Output is correct
4 Correct 60 ms 117692 KB Output is correct
5 Correct 61 ms 117828 KB Output is correct
6 Correct 54 ms 117836 KB Output is correct
7 Correct 60 ms 117828 KB Output is correct
8 Correct 55 ms 117700 KB Output is correct
9 Correct 54 ms 117708 KB Output is correct
10 Correct 55 ms 117924 KB Output is correct
11 Correct 58 ms 117668 KB Output is correct
12 Correct 55 ms 117716 KB Output is correct
13 Correct 57 ms 117656 KB Output is correct
14 Correct 55 ms 117696 KB Output is correct
15 Correct 57 ms 117716 KB Output is correct
16 Correct 55 ms 117708 KB Output is correct
17 Correct 59 ms 117828 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117668 KB Output is correct
2 Correct 54 ms 117704 KB Output is correct
3 Correct 1060 ms 290800 KB Output is correct
4 Correct 1229 ms 338572 KB Output is correct
5 Correct 965 ms 312940 KB Output is correct
6 Correct 899 ms 292984 KB Output is correct
7 Correct 968 ms 313008 KB Output is correct
8 Correct 1335 ms 337188 KB Output is correct
9 Correct 970 ms 303952 KB Output is correct
10 Correct 1750 ms 408584 KB Output is correct
11 Correct 610 ms 223964 KB Output is correct
12 Correct 639 ms 220656 KB Output is correct
13 Correct 1481 ms 377712 KB Output is correct
14 Correct 468 ms 207596 KB Output is correct
15 Correct 456 ms 198772 KB Output is correct
16 Correct 437 ms 198656 KB Output is correct
17 Correct 423 ms 196228 KB Output is correct
18 Correct 930 ms 220628 KB Output is correct
19 Correct 70 ms 121452 KB Output is correct
20 Correct 237 ms 156732 KB Output is correct
21 Correct 388 ms 191120 KB Output is correct
22 Correct 453 ms 198628 KB Output is correct
23 Correct 604 ms 213356 KB Output is correct
24 Correct 453 ms 197636 KB Output is correct
25 Correct 430 ms 194592 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 137384 KB Output is correct
2 Execution timed out 4089 ms 797232 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 137384 KB Output is correct
2 Execution timed out 4089 ms 797232 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 117708 KB Output is correct
2 Correct 53 ms 117704 KB Output is correct
3 Correct 54 ms 117644 KB Output is correct
4 Correct 60 ms 117692 KB Output is correct
5 Correct 61 ms 117828 KB Output is correct
6 Correct 54 ms 117836 KB Output is correct
7 Correct 60 ms 117828 KB Output is correct
8 Correct 55 ms 117700 KB Output is correct
9 Correct 54 ms 117708 KB Output is correct
10 Correct 55 ms 117924 KB Output is correct
11 Correct 58 ms 117668 KB Output is correct
12 Correct 55 ms 117716 KB Output is correct
13 Correct 57 ms 117656 KB Output is correct
14 Correct 55 ms 117696 KB Output is correct
15 Correct 57 ms 117716 KB Output is correct
16 Correct 55 ms 117708 KB Output is correct
17 Correct 59 ms 117828 KB Output is correct
18 Correct 58 ms 117668 KB Output is correct
19 Correct 54 ms 117704 KB Output is correct
20 Correct 1060 ms 290800 KB Output is correct
21 Correct 1229 ms 338572 KB Output is correct
22 Correct 965 ms 312940 KB Output is correct
23 Correct 899 ms 292984 KB Output is correct
24 Correct 968 ms 313008 KB Output is correct
25 Correct 1335 ms 337188 KB Output is correct
26 Correct 970 ms 303952 KB Output is correct
27 Correct 1750 ms 408584 KB Output is correct
28 Correct 610 ms 223964 KB Output is correct
29 Correct 639 ms 220656 KB Output is correct
30 Correct 1481 ms 377712 KB Output is correct
31 Correct 468 ms 207596 KB Output is correct
32 Correct 456 ms 198772 KB Output is correct
33 Correct 437 ms 198656 KB Output is correct
34 Correct 423 ms 196228 KB Output is correct
35 Correct 930 ms 220628 KB Output is correct
36 Correct 70 ms 121452 KB Output is correct
37 Correct 237 ms 156732 KB Output is correct
38 Correct 388 ms 191120 KB Output is correct
39 Correct 453 ms 198628 KB Output is correct
40 Correct 604 ms 213356 KB Output is correct
41 Correct 453 ms 197636 KB Output is correct
42 Correct 430 ms 194592 KB Output is correct
43 Correct 151 ms 137384 KB Output is correct
44 Execution timed out 4089 ms 797232 KB Time limit exceeded
45 Halted 0 ms 0 KB -