oj.uz

Submission #258166

# Submission time Handle Problem Language Result Execution time Memory
258166 2020-08-05T13:19:53 Z atoiz Sky Walking (IOI19_walk) C++14
43 / 100
 1702 ms 85444 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]) {
		if (L[w] < start) st[0][0].insert(Y[w], 0), st[0][1].insert(Y[w], Y[w]);
		if (R[w] > start) 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 - 1) {
		ll leftBest = st[0][0].get(0, H[leftBorder], false), rightBest = st[1][0].get(0, H[rightBorder], false);
		bool k = leftBest > rightBest;
		if (leftBorder == 0) k = 1;
		if (rightBorder == N - 1) k = 0;
 
		int col = (k == 0 ? --leftBorder : ++rightBorder);
 
		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);

		// 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]) {
			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]);
			}
		}
	}
 
	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 0 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 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 0 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
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 1079 ms 71412 KB Output is correct
4 Correct 1254 ms 81224 KB Output is correct
5 Correct 646 ms 65592 KB Output is correct
6 Correct 710 ms 67136 KB Output is correct
7 Correct 699 ms 65924 KB Output is correct
8 Correct 1039 ms 72644 KB Output is correct
9 Correct 1014 ms 80948 KB Output is correct
10 Correct 1214 ms 82968 KB Output is correct
11 Correct 1038 ms 76224 KB Output is correct
12 Correct 1119 ms 85420 KB Output is correct
13 Correct 1321 ms 85444 KB Output is correct
14 Correct 984 ms 80128 KB Output is correct
15 Incorrect 787 ms 45108 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 101 ms 10352 KB Output is correct
2 Correct 979 ms 70080 KB Output is correct
3 Correct 1143 ms 71452 KB Output is correct
4 Correct 1291 ms 79800 KB Output is correct
5 Correct 1159 ms 78276 KB Output is correct
6 Correct 1237 ms 79716 KB Output is correct
7 Correct 597 ms 45500 KB Output is correct
8 Correct 992 ms 81992 KB Output is correct
9 Correct 1025 ms 80616 KB Output is correct
10 Correct 594 ms 52064 KB Output is correct
11 Correct 22 ms 5316 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 979 ms 70080 KB Output is correct
3 Correct 1143 ms 71452 KB Output is correct
4 Correct 1291 ms 79800 KB Output is correct
5 Correct 1159 ms 78276 KB Output is correct
6 Correct 1237 ms 79716 KB Output is correct
7 Correct 597 ms 45500 KB Output is correct
8 Correct 992 ms 81992 KB Output is correct
9 Correct 1025 ms 80616 KB Output is correct
10 Correct 594 ms 52064 KB Output is correct
11 Correct 22 ms 5316 KB Output is correct
12 Correct 1128 ms 71016 KB Output is correct
13 Correct 1286 ms 79332 KB Output is correct
14 Correct 1430 ms 77804 KB Output is correct
15 Correct 739 ms 42316 KB Output is correct
16 Correct 1046 ms 42332 KB Output is correct
17 Correct 910 ms 42440 KB Output is correct
18 Correct 775 ms 42232 KB Output is correct
19 Correct 872 ms 42184 KB Output is correct
20 Correct 754 ms 44408 KB Output is correct
21 Correct 144 ms 10880 KB Output is correct
22 Correct 802 ms 60168 KB Output is correct
23 Correct 776 ms 61524 KB Output is correct
24 Correct 752 ms 65500 KB Output is correct
25 Correct 753 ms 67368 KB Output is correct
26 Correct 715 ms 72292 KB Output is correct
27 Correct 1337 ms 78148 KB Output is correct
28 Correct 1220 ms 79176 KB Output is correct
29 Correct 1702 ms 79072 KB Output is correct
30 Correct 728 ms 45120 KB Output is correct
31 Correct 1535 ms 80540 KB Output is correct
32 Correct 590 ms 37912 KB Output is correct
33 Correct 641 ms 39456 KB Output is correct
34 Correct 696 ms 51908 KB Output is correct
35 Correct 685 ms 43784 KB Output is correct
36 Correct 696 ms 38368 KB Output is correct
37 Correct 255 ms 30900 KB Output is correct
38 Correct 285 ms 35288 KB Output is correct
39 Correct 717 ms 56036 KB Output is correct
40 Correct 657 ms 35368 KB Output is correct
41 Correct 352 ms 31900 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 0 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 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 0 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 1079 ms 71412 KB Output is correct
21 Correct 1254 ms 81224 KB Output is correct
22 Correct 646 ms 65592 KB Output is correct
23 Correct 710 ms 67136 KB Output is correct
24 Correct 699 ms 65924 KB Output is correct
25 Correct 1039 ms 72644 KB Output is correct
26 Correct 1014 ms 80948 KB Output is correct
27 Correct 1214 ms 82968 KB Output is correct
28 Correct 1038 ms 76224 KB Output is correct
29 Correct 1119 ms 85420 KB Output is correct
30 Correct 1321 ms 85444 KB Output is correct
31 Correct 984 ms 80128 KB Output is correct
32 Incorrect 787 ms 45108 KB Output isn't correct
33 Halted 0 ms 0 KB -