oj.uz

Submission #768631

# Submission time Handle Problem Language Result Execution time Memory
768631 2023-06-28T10:15:00 Z marvinthang Sky Walking (IOI19_walk) C++17
33 / 100
 519 ms 52120 KB 
#include "walk.h"
/*************************************
*    author: marvinthang             *
*    created: 28.06.2023 15:43:09    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

// end of template

const long long INF = 1e18;

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 = l.size();
	vector <vector <int>> startAt(n), endAt(n);
	REP(i, m) {
		startAt[l[i]].push_back(i);
		endAt[r[i]].push_back(i);
	}
	map <int, int> heights;
	vector <vector <int>> yy(n);
	vector <vector <pair <int, int>>> adj;
	vector <int> pref(n);
	auto add_edge = [&] (int u, int v, int w) {
		adj[u].emplace_back(w, v);
		adj[v].emplace_back(w, u);
	};
	REP(i, n) {
		if (i) pref[i] = pref[i - 1] + yy[i - 1].size();
		if (i == s || i == g) {
			yy[i].push_back(0);
			for (int j: startAt[i]) yy[i].push_back(y[j]);
			for (int j: endAt[i]) yy[i].push_back(y[j]);
			for (auto it: heights) yy[i].push_back(it.fi);
			sort(ALL(yy[i]));
			yy[i].erase(unique(ALL(yy[i])), yy[i].end());
			adj.resize(pref[i] + yy[i].size());
			REP(j, (int) yy[i].size() - 1) add_edge(pref[i] + j, pref[i] + j + 1, yy[i][j + 1] - yy[i][j]);
		} else {
			for (int j: startAt[i]) {
				yy[i].push_back(y[j]);
				auto it = heights.lower_bound(y[j]);
				if (it != heights.begin()) yy[i].push_back(prev(it)->fi);
			}
			for (int j: endAt[i]) {
				yy[i].push_back(y[j]);
				auto it = heights.lower_bound(y[j]);
				if (it != heights.begin()) yy[i].push_back(prev(it)->fi);
			}
			sort(ALL(yy[i]));
			yy[i].erase(unique(ALL(yy[i])), yy[i].end());
			adj.resize(pref[i] + yy[i].size());
			for (int j: startAt[i]) {
				int p = lower_bound(ALL(yy[i]), y[j]) - yy[i].begin();
				if (p) add_edge(pref[i] + p - 1, pref[i] + p, yy[i][p] - yy[i][p - 1]);
			}
			for (int j: endAt[i]) {
				int p = lower_bound(ALL(yy[i]), y[j]) - yy[i].begin();
				if (p) add_edge(pref[i] + p - 1, pref[i] + p, yy[i][p] - yy[i][p - 1]);
			}
		}

		REP(j, yy[i].size()) if (heights.count(yy[i][j])) {
			int k = heights[yy[i][j]];
			int p = lower_bound(ALL(yy[k]), yy[i][j]) - yy[k].begin();
			add_edge(pref[k] + p, pref[i] + j, x[i] - x[k]);
			heights[yy[i][j]] = i;
		}

		for (int j: endAt[i]) heights.erase(y[j]);
		for (int j: startAt[i]) heights[y[j]] = i;
	}
	priority_queue <pair <long long, int>, vector <pair <long long, int>>, greater <pair <long long, int>>> pq;
	vector <long long> dist(adj.size(), INF);
	pq.emplace(dist[pref[s]] = 0, pref[s]);
	while (!pq.empty()) {
		auto [du, u] = pq.top(); pq.pop();
		if (du != dist[u]) continue;
		for (auto [w, v]: adj[u]) if (minimize(dist[v], du + w)) pq.emplace(dist[v], v);
	}
	return dist[pref[g]] < INF ? dist[pref[g]] : -1;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9596 KB Output is correct
2 Correct 325 ms 36284 KB Output is correct
3 Correct 337 ms 35760 KB Output is correct
4 Correct 387 ms 47320 KB Output is correct
5 Correct 509 ms 48460 KB Output is correct
6 Correct 464 ms 48620 KB Output is correct
7 Correct 159 ms 29928 KB Output is correct
8 Correct 109 ms 33460 KB Output is correct
9 Correct 452 ms 49984 KB Output is correct
10 Correct 150 ms 33224 KB Output is correct
11 Correct 10 ms 4716 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9596 KB Output is correct
2 Correct 325 ms 36284 KB Output is correct
3 Correct 337 ms 35760 KB Output is correct
4 Correct 387 ms 47320 KB Output is correct
5 Correct 509 ms 48460 KB Output is correct
6 Correct 464 ms 48620 KB Output is correct
7 Correct 159 ms 29928 KB Output is correct
8 Correct 109 ms 33460 KB Output is correct
9 Correct 452 ms 49984 KB Output is correct
10 Correct 150 ms 33224 KB Output is correct
11 Correct 10 ms 4716 KB Output is correct
12 Correct 339 ms 35636 KB Output is correct
13 Correct 324 ms 47204 KB Output is correct
14 Correct 496 ms 48484 KB Output is correct
15 Correct 282 ms 41524 KB Output is correct
16 Correct 279 ms 42460 KB Output is correct
17 Correct 312 ms 46524 KB Output is correct
18 Correct 265 ms 41388 KB Output is correct
19 Correct 281 ms 43596 KB Output is correct
20 Correct 189 ms 29724 KB Output is correct
21 Correct 23 ms 9672 KB Output is correct
22 Correct 209 ms 39240 KB Output is correct
23 Correct 183 ms 39396 KB Output is correct
24 Correct 148 ms 32808 KB Output is correct
25 Correct 159 ms 39272 KB Output is correct
26 Correct 116 ms 30204 KB Output is correct
27 Correct 519 ms 52120 KB Output is correct
28 Correct 241 ms 46772 KB Output is correct
29 Correct 466 ms 48708 KB Output is correct
30 Correct 158 ms 29948 KB Output is correct
31 Correct 439 ms 49936 KB Output is correct
32 Correct 126 ms 31524 KB Output is correct
33 Correct 142 ms 33216 KB Output is correct
34 Correct 177 ms 40976 KB Output is correct
35 Correct 161 ms 39028 KB Output is correct
36 Correct 123 ms 36276 KB Output is correct
37 Correct 114 ms 32916 KB Output is correct
38 Correct 107 ms 36700 KB Output is correct
39 Correct 216 ms 43340 KB Output is correct
40 Correct 110 ms 35908 KB Output is correct
41 Correct 106 ms 34376 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -