Submission #258249

#	Time	Username	Problem	Language	Result	Execution time	Memory
258249		atoiz	Sky Walking (IOI19_walk)	C++14	100 / 100	2178 ms	83776 KiB

walk

#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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43