oj.uz

Submission #258238

# Submission time Handle Problem Language Result Execution time Memory
258238 2020-08-05T15:11:09 Z atoiz Sky Walking (IOI19_walk) C++14
43 / 100
 1672 ms 85548 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) {
		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 (auto upd : updates[col]) {
				// cout << "." << endl;
				int y = upd.first;
				ll c = upd.second;
				// cout << "upd " << y << ' ' << c << endl;
				st[k][0].minimize(y, H[col], c), st[k][1].minimize(0, y, c + y);
			}


			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 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 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 288 KB Output is correct
17 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1116 ms 72492 KB Output is correct
4 Correct 1224 ms 84424 KB Output is correct
5 Correct 712 ms 64952 KB Output is correct
6 Correct 776 ms 66872 KB Output is correct
7 Correct 708 ms 65516 KB Output is correct
8 Correct 1107 ms 72444 KB Output is correct
9 Correct 1164 ms 80496 KB Output is correct
10 Correct 1522 ms 82244 KB Output is correct
11 Correct 1115 ms 76096 KB Output is correct
12 Correct 1042 ms 84596 KB Output is correct
13 Correct 1219 ms 84808 KB Output is correct
14 Correct 986 ms 79488 KB Output is correct
15 Incorrect 782 ms 45020 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 10608 KB Output is correct
2 Correct 1066 ms 71084 KB Output is correct
3 Correct 1214 ms 72740 KB Output is correct
4 Correct 1311 ms 83140 KB Output is correct
5 Correct 1269 ms 81608 KB Output is correct
6 Correct 1270 ms 83072 KB Output is correct
7 Correct 613 ms 47928 KB Output is correct
8 Correct 1008 ms 85548 KB Output is correct
9 Correct 1335 ms 84352 KB Output is correct
10 Correct 703 ms 54884 KB Output is correct
11 Correct 24 ms 5888 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 10608 KB Output is correct
2 Correct 1066 ms 71084 KB Output is correct
3 Correct 1214 ms 72740 KB Output is correct
4 Correct 1311 ms 83140 KB Output is correct
5 Correct 1269 ms 81608 KB Output is correct
6 Correct 1270 ms 83072 KB Output is correct
7 Correct 613 ms 47928 KB Output is correct
8 Correct 1008 ms 85548 KB Output is correct
9 Correct 1335 ms 84352 KB Output is correct
10 Correct 703 ms 54884 KB Output is correct
11 Correct 24 ms 5888 KB Output is correct
12 Correct 1326 ms 72520 KB Output is correct
13 Correct 1672 ms 83052 KB Output is correct
14 Correct 1642 ms 81480 KB Output is correct
15 Correct 982 ms 45640 KB Output is correct
16 Correct 1217 ms 45896 KB Output is correct
17 Correct 1153 ms 45892 KB Output is correct
18 Correct 1155 ms 45692 KB Output is correct
19 Correct 896 ms 46020 KB Output is correct
20 Correct 881 ms 47040 KB Output is correct
21 Correct 154 ms 12400 KB Output is correct
22 Correct 958 ms 63328 KB Output is correct
23 Correct 781 ms 64856 KB Output is correct
24 Correct 779 ms 68628 KB Output is correct
25 Correct 944 ms 70812 KB Output is correct
26 Correct 745 ms 76004 KB Output is correct
27 Correct 1419 ms 82128 KB Output is correct
28 Correct 1509 ms 83032 KB Output is correct
29 Correct 1584 ms 83044 KB Output is correct
30 Correct 813 ms 47840 KB Output is correct
31 Correct 1459 ms 84480 KB Output is correct
32 Correct 621 ms 40656 KB Output is correct
33 Correct 639 ms 42276 KB Output is correct
34 Correct 777 ms 51524 KB Output is correct
35 Correct 749 ms 43392 KB Output is correct
36 Correct 761 ms 38108 KB Output is correct
37 Correct 285 ms 30900 KB Output is correct
38 Correct 405 ms 34904 KB Output is correct
39 Correct 803 ms 55744 KB Output is correct
40 Correct 607 ms 35288 KB Output is correct
41 Correct 372 ms 32024 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 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 288 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 1116 ms 72492 KB Output is correct
21 Correct 1224 ms 84424 KB Output is correct
22 Correct 712 ms 64952 KB Output is correct
23 Correct 776 ms 66872 KB Output is correct
24 Correct 708 ms 65516 KB Output is correct
25 Correct 1107 ms 72444 KB Output is correct
26 Correct 1164 ms 80496 KB Output is correct
27 Correct 1522 ms 82244 KB Output is correct
28 Correct 1115 ms 76096 KB Output is correct
29 Correct 1042 ms 84596 KB Output is correct
30 Correct 1219 ms 84808 KB Output is correct
31 Correct 986 ms 79488 KB Output is correct
32 Incorrect 782 ms 45020 KB Output isn't correct
33 Halted 0 ms 0 KB -