| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 258163 |
2020-08-05T13:14:51 Z |
atoiz |
Sky Walking (IOI19_walk) |
C++14 |
|
1029 ms |
70540 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);
if (~i) st[k][0].minimize(Y[i], H[col], curCost + Y[w] - Y[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;
}
| # |
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 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1029 ms |
70540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
9972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
9972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
