oj.uz

Submission #258061

# Submission time Handle Problem Language Result Execution time Memory
258061 2020-08-05T09:41:16 Z atoiz Sky Walking (IOI19_walk) C++14
0 / 100
 4000 ms 70340 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 <=

int CC = 0;

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, md = (lo + hi) >> 1;
				lazy[lc] = min(lazy[lc], lazy[rt]), lazy[rc] = min(lazy[rc], lazy[rt]);
				push(lc, lo, md), push(rc, md + 1, hi);
			}
		}
		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) {
				assert(valY[lo] == y);
				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) {
		if (valY[hi] < l || r < valY[lo] || !cnt[rt]) return INFLL;
		push(rt, lo, hi);
		if (lo == hi) return arr[lo];
		int lc = rt << 1, rc = rt << 1 | 1, md = (lo + hi) >> 1;

		ll ans = INFLL;
		if (minY) {
			if (cnt[lc] && l <= valY[md]) ans = get(l, r, minY, lc, lo, md);
			if (ans == INFLL && cnt[rc] && valY[md + 1] <= r) ans = get(l, r, minY, rc, md + 1, hi);
		} else {
			if (cnt[rc] && valY[md + 1] <= r) ans = get(l, r, minY, rc, md + 1, hi);
			if (ans == INFLL && cnt[lc] && l <= valY[md]) ans = get(l, r, minY, lc, lo, md);
		}
		return ans;
	}
	ll get(int l, int r, bool minY) { return get(l, r, minY, 1, 0, T - 1); }
};

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;
	while (leftBorder > 0 || rightBorder < N - 1) {
		ll leftBest = st[0][0].get(0, MAXY, false), rightBest = st[1][0].get(0, MAXY, 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]);
			st[k][0].insert(Y[w], INFLL), st[k][1].insert(Y[w], INFLL);
			// cout << "pre dist " << col << ' ' << Y[w] << ": " << curCost << endl;
		}

		for (auto upd : updates[col]) {
			int y = upd.first;
			ll c = upd.second;
			st[k][0].minimize(y, MAXY, c), st[k][1].minimize(0, y, c + y);
		}
		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]);
			// 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]) st[k][0].remove(Y[w]), st[k][1].remove(Y[w]);
	}

	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;
	// cout << "CC = " << CC << endl;
	return ans;
}

Subtask #1
0 / 10.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 0 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 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 0 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 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Incorrect 0 ms 256 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.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 Incorrect 3133 ms 70340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9968 KB Output is correct
2 Execution timed out 4083 ms 63840 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9968 KB Output is correct
2 Execution timed out 4083 ms 63840 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.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 0 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 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 0 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 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Incorrect 0 ms 256 KB Output isn't correct
17 Halted 0 ms 0 KB -