oj.uz

Submission #258249

# Submission time Handle Problem Language Result Execution time Memory
258249 2020-08-05T15:20:31 Z atoiz Sky Walking (IOI19_walk) C++14
100 / 100
 2178 ms 83776 KB 
#include "walk.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <cassert>
#include <numeric>
 
using namespace std;
using ll = long long;
 
const int MAXY = 1000100100;
const ll INFLL = 1e16;
int N, M, T;
vector<int> X, H, L, R, Y;
vector<int> valY;
 
int dist(int i, int j) { return abs(X[i] - X[j]); }
// int pos(int y) { return (int) (upper_bound(valY.begin(), valY.end(), y) - valY.begin() - 1); } // first <=
 
struct SegmentTree {
	vector<ll> lazy, arr;
	vector<int> cnt;
	SegmentTree(): lazy((T + 2) * 4, INFLL), arr((T + 2) * 4, INFLL), cnt((T + 2) * 4, 0) {}
 
	void push(int rt, int lo, int hi) {
		if (lazy[rt] != INFLL && cnt[rt]) {
			if (lo == hi) arr[lo] = min(arr[lo], lazy[rt]);
			else {
				int lc = rt << 1, rc = rt << 1 | 1;
				lazy[lc] = min(lazy[lc], lazy[rt]), lazy[rc] = min(lazy[rc], lazy[rt]);
			}
		}
		lazy[rt] = INFLL;
	}
 
	void insert(int y, ll c) {
		int rt = 1, lo = 0, hi = T - 1;
		while (true) {
			push(rt, lo, hi);
			++cnt[rt];
			if (lo == hi) {
				assert(valY[lo] == y);
				arr[lo] = min(arr[lo], c);
				break;
			}
			int md = (lo + hi) >> 1;
			(y <= valY[md]) ? (rt = rt << 1, hi = md) : (rt = rt << 1 | 1, lo = md + 1);
		}
	}
 
	void remove(int y) {
		int rt = 1, lo = 0, hi = T - 1;
		while (true) {
			push(rt, lo, hi);
			--cnt[rt];
			if (lo == hi) {
				if (cnt[rt] == 0) arr[lo] = INFLL;
				break;
			}
			int md = (lo + hi) >> 1;
			(y <= valY[md]) ? (rt = rt << 1, hi = md) : (rt = rt << 1 | 1, lo = md + 1);
		}
	}
 
	void minimize(int l, int r, ll c, int rt, int lo, int hi) {
		if (valY[hi] < l || r < valY[lo] || !cnt[rt] || lazy[rt] <= c) return;
		push(rt, lo, hi);
		if (l <= valY[lo] && valY[hi] <= r) return lazy[rt] = min(lazy[rt], c), void(0);
		int lc = rt << 1, rc = rt << 1 | 1, md = (lo + hi) >> 1;
		minimize(l, r, c, lc, lo, md), minimize(l, r, c, rc, md + 1, hi);
	}
	void minimize(int l, int r, ll c) { minimize(l, r, c, 1, 0, T - 1); }
 
	ll get(int l, int r, bool minY, int rt, int lo, int hi, bool &found) {
		if (valY[hi] < l || r < valY[lo] || !cnt[rt] || found) return INFLL;
		push(rt, lo, hi);
		if (lo == hi) return found = true, arr[lo];
		int lc = rt << 1, rc = rt << 1 | 1, md = (lo + hi) >> 1;
 
		ll ans = INFLL;
		if (minY) {
			ans = get(l, r, minY, lc, lo, md, found);
			if (!found) ans = get(l, r, minY, rc, md + 1, hi, found);
		} else {
			ans = get(l, r, minY, rc, md + 1, hi, found);
			if (!found) ans = get(l, r, minY, lc, lo, md, found);
		}
		return ans;
	}
	ll get(int l, int r, bool minY) { bool found = false; return get(l, r, minY, 1, 0, T - 1, found); }
 
	int getPos(int l, int r, bool minY, int rt, int lo, int hi, bool &found) {
		if (valY[hi] < l || r < valY[lo] || !cnt[rt] || found) return -1;
		push(rt, lo, hi);
		if (lo == hi) return found = true, lo;
		int lc = rt << 1, rc = rt << 1 | 1, md = (lo + hi) >> 1;
 
		int ans = -1;
		if (minY) {
			ans = getPos(l, r, minY, lc, lo, md, found);
			if (!found) ans = getPos(l, r, minY, rc, md + 1, hi, found);
		} else {
			ans = getPos(l, r, minY, rc, md + 1, hi, found);
			if (!found) ans = getPos(l, r, minY, lc, lo, md, found);
		}
		return ans;
	}
	int getPos(int l, int r, bool minY) { bool found = false; return getPos(l, r, minY, 1, 0, T - 1, found); }
};
 
vector<vector<pair<int, ll>>> solve(int start) {
	// cout << "solve " << start << endl;
	vector<vector<pair<int, ll>>> ans(M);
 
	vector<vector<int>> walksAdd(N), walksRem(N);
	vector<int> walkL(M, -1), walkR(M, -1);
	vector<int> walkIDs(M);
	iota(walkIDs.begin(), walkIDs.end(), 0);
	sort(walkIDs.begin(), walkIDs.end(), [&](int i, int j) { return Y[i] < Y[j]; });
	vector<int> lCols, rCols;
	for (int x = 0; x <= start; lCols.push_back(x++)) while (!lCols.empty() && H[lCols.back()] <= H[x]) lCols.pop_back();
	for (int x = N - 1; x >= start; rCols.push_back(x--)) while (!rCols.empty() && H[rCols.back()] <= H[x]) rCols.pop_back();
	for (int w : walkIDs) {
		if (L[w] <= start && start <= R[w] && Y[w] <= H[start]) { 
			walksAdd[walkL[w] = walkR[w] = start].push_back(w);
			walksRem[L[w]].push_back(w), walksRem[R[w]].push_back(w);
			continue; 
		}
 
		while (!lCols.empty() && H[lCols.back()] < Y[w]) lCols.pop_back();
		while (!rCols.empty() && H[rCols.back()] < Y[w]) rCols.pop_back();
		if (!rCols.empty() && rCols.back() <= L[w]) walksAdd[L[w]].push_back(w), walksRem[R[w]].push_back(w);
		else if (!lCols.empty() && lCols.back() >= R[w]) walksAdd[R[w]].push_back(w), walksRem[L[w]].push_back(w);
		else {
			if (!lCols.empty() && L[w] <= lCols.back()) walksAdd[walkL[w] = lCols.back()].push_back(w), walksRem[L[w]].push_back(w);
			if (!rCols.empty() && R[w] >= rCols.back()) walksAdd[walkR[w] = rCols.back()].push_back(w), walksRem[R[w]].push_back(w);
		}
	}
 
	// for (int x = 0; x < N; ++x) {
	// 	cout << x << ":\n";
	// 	for (auto w : walksRem[x]) cout << L[w] << ' ' << R[w] << ' ' << Y[w] << endl;
	// }
 
	vector<vector<SegmentTree>> st(2, vector<SegmentTree>(2, SegmentTree()));
	for (int w : walksAdd[start]) {
		st[0][0].insert(Y[w], 0), st[0][1].insert(Y[w], Y[w]);
		st[1][0].insert(Y[w], 0), st[1][1].insert(Y[w], Y[w]);
		// ans[w].emplace_back(start, 0);
	}
 
	vector<vector<pair<int, ll>>> updates(N);
	int leftBorder = start, rightBorder = start;
	vector<vector<int>> mergers(2, vector<int>(1, start));
	while (leftBorder >= 0 || rightBorder < N) {
		if (leftBorder >= 0) {
			for (auto upd : updates[leftBorder]) {
				// cout << "." << endl;
				int y = upd.first;
				ll c = upd.second;
				// cout << "upd " << y << ' ' << c << endl;
				st[0][0].minimize(y, H[leftBorder], c), st[0][1].minimize(0, y, c + y);
			}
			updates[leftBorder].clear();
		}
		if (rightBorder <= N - 1) {
			for (auto upd : updates[rightBorder]) {
				// cout << "." << endl;
				int y = upd.first;
				ll c = upd.second;
				// cout << "upd " << y << ' ' << c << endl;
				st[1][0].minimize(y, H[rightBorder], c), st[1][1].minimize(0, y, c + y);
			}
			updates[rightBorder].clear();
		}


		ll leftBest = st[0][0].get(0, MAXY, false), rightBest = st[1][0].get(0, MAXY, false);
		bool k = leftBest > rightBest;
		if (leftBorder == -1) k = 1;
		if (rightBorder == N) k = 0;
 
		int col = (k == 0 ? leftBorder-- : rightBorder++);

		// cout << "T" << endl;
		for (int w : walksAdd[col]) {
			ll curCost = min(st[k][0].get(Y[w], Y[w], false), st[k][1].get(Y[w], Y[w], false) - Y[w]);
			if (curCost == INFLL - Y[w]) curCost = INFLL;
			// cout << "dist " << col << ' ' << Y[w] << ": " << curCost << endl;
			ans[w].emplace_back(col, curCost);
 
			if (~walkL[w] && ~walkR[w] && walkL[w] < start && start < walkR[w]) {
				if (col == walkL[w]) updates[walkR[w]].emplace_back(Y[w], curCost + X[start] - X[col]);
				if (col == walkR[w]) updates[walkL[w]].emplace_back(Y[w], curCost + X[col] - X[start]);
			}
		}
 
		for (int w : walksRem[col]) {
			if ((k == 0) ? (L[w] != col) : (R[w] != col)) continue;
			ll curCost = min(st[k][0].get(Y[w], Y[w], false), st[k][1].get(Y[w], Y[w], false) - Y[w]);
			if (curCost == INFLL - Y[w]) curCost = INFLL;
			st[k][0].remove(Y[w]), st[k][1].remove(Y[w]);
			if (curCost != INFLL) {
				int i = st[k][0].getPos(0, Y[w] - 1, false);
				st[k][0].minimize(Y[w], H[col], curCost);
				if (~i) st[k][0].minimize(valY[i], valY[i], curCost + Y[w] - valY[i]);
			}
		}
 
 		(k == 0 ? --col : ++col);
 		if (col != -1 && col != N) {
			for (int w : walksAdd[col]) {
				ll curCost = min(st[k][0].get(0, Y[w], false), st[k][1].get(Y[w], H[col], true) - Y[w]);
				if (curCost == INFLL - Y[w]) curCost = INFLL;
				st[k][0].insert(Y[w], curCost), st[k][1].insert(Y[w], curCost + Y[w]);
				// cout << "pre dist " << col << ' ' << Y[w] << ": " << curCost << endl;
			}
	 
			// cout << "S" << endl;

			for (; !mergers[k].empty() && H[mergers[k].back()] <= H[col]; mergers[k].pop_back()) {
				int prv = mergers[k].back();
				ll curCost = st[k][1].get(H[prv] + 1, H[col], true);
				st[k][1].minimize(0, H[prv], curCost);
			}
			mergers[k].push_back(col);
		}
	}
 
	return ans;
}
 
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int t) {
	N = (int) x.size(), M = (int) y.size();
	X = x, H = h, L = l, R = r, Y = y;
	valY = Y;
	sort(valY.begin(), valY.end()), valY.erase(unique(valY.begin(), valY.end()), valY.end());
	T = (int) valY.size();
 
	vector<vector<pair<int, ll>>> ansS = solve(s);
	vector<vector<pair<int, ll>>> ansT = solve(t);
	ll ans = INFLL;
	for (int j = 0; j < M; ++j) {
		for (auto p : ansS[j]) for (auto q : ansT[j]) {
			ll cur = 0;
			cur += (ll) Y[j] * 2;
			cur += (ll) dist(p.first, q.first) + dist(p.first, s) + dist(q.first, t);
			cur += (p.second + q.second) * 2;
			// if (cur == 27) cout << L[j] << ' ' << R[j] << ' ' << Y[j] << " - " << p.first << ' ' << q.first << endl;
			ans = min(ans, cur);
		}
	}
 
	if (ans == INFLL) ans = -1;
	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1082 ms 70852 KB Output is correct
4 Correct 1527 ms 80620 KB Output is correct
5 Correct 737 ms 62520 KB Output is correct
6 Correct 817 ms 64316 KB Output is correct
7 Correct 1020 ms 63056 KB Output is correct
8 Correct 1168 ms 70848 KB Output is correct
9 Correct 1109 ms 78352 KB Output is correct
10 Correct 1543 ms 79764 KB Output is correct
11 Correct 1326 ms 73640 KB Output is correct
12 Correct 1089 ms 82180 KB Output is correct
13 Correct 1314 ms 82248 KB Output is correct
14 Correct 981 ms 77200 KB Output is correct
15 Correct 890 ms 42372 KB Output is correct
16 Correct 670 ms 34936 KB Output is correct
17 Correct 624 ms 32348 KB Output is correct
18 Correct 969 ms 81180 KB Output is correct
19 Correct 42 ms 4388 KB Output is correct
20 Correct 439 ms 41952 KB Output is correct
21 Correct 386 ms 30888 KB Output is correct
22 Correct 395 ms 35208 KB Output is correct
23 Correct 838 ms 56052 KB Output is correct
24 Correct 613 ms 35492 KB Output is correct
25 Correct 388 ms 31896 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 10352 KB Output is correct
2 Correct 1155 ms 69796 KB Output is correct
3 Correct 1266 ms 70916 KB Output is correct
4 Correct 1608 ms 79300 KB Output is correct
5 Correct 1434 ms 77908 KB Output is correct
6 Correct 1454 ms 79284 KB Output is correct
7 Correct 666 ms 45260 KB Output is correct
8 Correct 1132 ms 81772 KB Output is correct
9 Correct 1344 ms 80664 KB Output is correct
10 Correct 795 ms 51932 KB Output is correct
11 Correct 23 ms 5532 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 10352 KB Output is correct
2 Correct 1155 ms 69796 KB Output is correct
3 Correct 1266 ms 70916 KB Output is correct
4 Correct 1608 ms 79300 KB Output is correct
5 Correct 1434 ms 77908 KB Output is correct
6 Correct 1454 ms 79284 KB Output is correct
7 Correct 666 ms 45260 KB Output is correct
8 Correct 1132 ms 81772 KB Output is correct
9 Correct 1344 ms 80664 KB Output is correct
10 Correct 795 ms 51932 KB Output is correct
11 Correct 23 ms 5532 KB Output is correct
12 Correct 1248 ms 70916 KB Output is correct
13 Correct 1578 ms 79404 KB Output is correct
14 Correct 1440 ms 77912 KB Output is correct
15 Correct 767 ms 42316 KB Output is correct
16 Correct 915 ms 42444 KB Output is correct
17 Correct 984 ms 42288 KB Output is correct
18 Correct 778 ms 42184 KB Output is correct
19 Correct 841 ms 42080 KB Output is correct
20 Correct 818 ms 44536 KB Output is correct
21 Correct 143 ms 10824 KB Output is correct
22 Correct 966 ms 60036 KB Output is correct
23 Correct 768 ms 61400 KB Output is correct
24 Correct 822 ms 65276 KB Output is correct
25 Correct 792 ms 67568 KB Output is correct
26 Correct 776 ms 72672 KB Output is correct
27 Correct 1575 ms 78436 KB Output is correct
28 Correct 1426 ms 79376 KB Output is correct
29 Correct 1644 ms 79332 KB Output is correct
30 Correct 856 ms 45244 KB Output is correct
31 Correct 1636 ms 80636 KB Output is correct
32 Correct 733 ms 37908 KB Output is correct
33 Correct 770 ms 39484 KB Output is correct
34 Correct 876 ms 49476 KB Output is correct
35 Correct 998 ms 41372 KB Output is correct
36 Correct 894 ms 35896 KB Output is correct
37 Correct 471 ms 28520 KB Output is correct
38 Correct 378 ms 32728 KB Output is correct
39 Correct 913 ms 53468 KB Output is correct
40 Correct 622 ms 32932 KB Output is correct
41 Correct 421 ms 29772 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 1082 ms 70852 KB Output is correct
21 Correct 1527 ms 80620 KB Output is correct
22 Correct 737 ms 62520 KB Output is correct
23 Correct 817 ms 64316 KB Output is correct
24 Correct 1020 ms 63056 KB Output is correct
25 Correct 1168 ms 70848 KB Output is correct
26 Correct 1109 ms 78352 KB Output is correct
27 Correct 1543 ms 79764 KB Output is correct
28 Correct 1326 ms 73640 KB Output is correct
29 Correct 1089 ms 82180 KB Output is correct
30 Correct 1314 ms 82248 KB Output is correct
31 Correct 981 ms 77200 KB Output is correct
32 Correct 890 ms 42372 KB Output is correct
33 Correct 670 ms 34936 KB Output is correct
34 Correct 624 ms 32348 KB Output is correct
35 Correct 969 ms 81180 KB Output is correct
36 Correct 42 ms 4388 KB Output is correct
37 Correct 439 ms 41952 KB Output is correct
38 Correct 386 ms 30888 KB Output is correct
39 Correct 395 ms 35208 KB Output is correct
40 Correct 838 ms 56052 KB Output is correct
41 Correct 613 ms 35492 KB Output is correct
42 Correct 388 ms 31896 KB Output is correct
43 Correct 101 ms 10352 KB Output is correct
44 Correct 1155 ms 69796 KB Output is correct
45 Correct 1266 ms 70916 KB Output is correct
46 Correct 1608 ms 79300 KB Output is correct
47 Correct 1434 ms 77908 KB Output is correct
48 Correct 1454 ms 79284 KB Output is correct
49 Correct 666 ms 45260 KB Output is correct
50 Correct 1132 ms 81772 KB Output is correct
51 Correct 1344 ms 80664 KB Output is correct
52 Correct 795 ms 51932 KB Output is correct
53 Correct 23 ms 5532 KB Output is correct
54 Correct 1248 ms 70916 KB Output is correct
55 Correct 1578 ms 79404 KB Output is correct
56 Correct 1440 ms 77912 KB Output is correct
57 Correct 767 ms 42316 KB Output is correct
58 Correct 915 ms 42444 KB Output is correct
59 Correct 984 ms 42288 KB Output is correct
60 Correct 778 ms 42184 KB Output is correct
61 Correct 841 ms 42080 KB Output is correct
62 Correct 818 ms 44536 KB Output is correct
63 Correct 143 ms 10824 KB Output is correct
64 Correct 966 ms 60036 KB Output is correct
65 Correct 768 ms 61400 KB Output is correct
66 Correct 822 ms 65276 KB Output is correct
67 Correct 792 ms 67568 KB Output is correct
68 Correct 776 ms 72672 KB Output is correct
69 Correct 1575 ms 78436 KB Output is correct
70 Correct 1426 ms 79376 KB Output is correct
71 Correct 1644 ms 79332 KB Output is correct
72 Correct 856 ms 45244 KB Output is correct
73 Correct 1636 ms 80636 KB Output is correct
74 Correct 733 ms 37908 KB Output is correct
75 Correct 770 ms 39484 KB Output is correct
76 Correct 876 ms 49476 KB Output is correct
77 Correct 998 ms 41372 KB Output is correct
78 Correct 894 ms 35896 KB Output is correct
79 Correct 471 ms 28520 KB Output is correct
80 Correct 378 ms 32728 KB Output is correct
81 Correct 913 ms 53468 KB Output is correct
82 Correct 622 ms 32932 KB Output is correct
83 Correct 421 ms 29772 KB Output is correct
84 Correct 127 ms 8708 KB Output is correct
85 Correct 1421 ms 72784 KB Output is correct
86 Correct 1794 ms 82044 KB Output is correct
87 Correct 124 ms 13960 KB Output is correct
88 Correct 174 ms 14064 KB Output is correct
89 Correct 132 ms 13940 KB Output is correct
90 Correct 50 ms 3764 KB Output is correct
91 Correct 2 ms 512 KB Output is correct
92 Correct 56 ms 3820 KB Output is correct
93 Correct 601 ms 34576 KB Output is correct
94 Correct 147 ms 12528 KB Output is correct
95 Correct 797 ms 65848 KB Output is correct
96 Correct 885 ms 65216 KB Output is correct
97 Correct 873 ms 69620 KB Output is correct
98 Correct 772 ms 70796 KB Output is correct
99 Correct 1982 ms 83776 KB Output is correct
100 Correct 1761 ms 83016 KB Output is correct
101 Correct 2178 ms 83524 KB Output is correct
102 Correct 882 ms 47800 KB Output is correct
103 Correct 785 ms 40612 KB Output is correct
104 Correct 693 ms 42156 KB Output is correct
105 Correct 837 ms 52292 KB Output is correct
106 Correct 1217 ms 56452 KB Output is correct
107 Correct 1147 ms 57020 KB Output is correct
108 Correct 89 ms 6844 KB Output is correct
109 Correct 1226 ms 66216 KB Output is correct
110 Correct 1165 ms 81748 KB Output is correct
111 Correct 1615 ms 81164 KB Output is correct
112 Correct 879 ms 39596 KB Output is correct
113 Correct 849 ms 38816 KB Output is correct