| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 771841 | green_gold_dog | Maze (JOI23_ho_t3) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1'000'000'000;
template<typename T>
bool assign_min(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_max(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
struct segment_tree {
vector<bool> tree;
ll size;
segment_tree(ll n) {
size = 1;
while (size < n) {
size *= 2;
}
tree.resize(size * 2, false);
}
vector<ll> set(ll l, ll r) {
vector<ll> ans;
set(1, 0, size, l, r, ans);
return ans;
}
void set(ll v, ll l, ll r, ll ql, ll qr, vector<ll>& ans) {
if (tree[v]) {
return;
}
if (r <= ql || qr <= l) {
return;
}
if (r - l == 1) {
ans.push_back(l);
tree[v] = true;
return;
}
ll mid = (l + r) / 2;
set(v * 2, l, mid, ql, qr, ans);
set(v * 2 + 1, mid, r, ql, qr, ans);
tree[v] = tree[v * 2] && tree[v * 2 + 1];
}
};
struct segment_tree_am {
vector<ll> m, tree;
ll size;
segment_tree_am(ll n) {
size = 1;
while (size < n) {
size *= 2;
}
m.resize(size * 2, 0);
tree.resize(size * 2, 0);
}
bool get(ll l, ll r) {
return get(1, 0, size, l, r);
}
bool get(ll v, ll l, ll r, ll ql, ll qr) {
if (tree[v] != 0) {
return false;
}
if (ql <= l && r <= qr) {
return true;
}
if (qr <= l || r <= ql) {
return false;
}
ll mid = (l + r) / 2;
return get(v * 2, l, mid, ql, qr) || get(v * 2 + 1, mid, r, ql, qr);
}
void add(ll l, ll r, ll x) {
add(1, 0, size, l, r, x);
}
void add(ll v, ll l, ll r, ll ql, ll qr, ll x) {
if (ql <= l && r <= qr) {
tree[v] += x;
m[v] += x;
return;
}
if (qr <= l || r <= ql) {
return;
}
ll mid = (l + r) / 2;
add(v * 2, l, mid, ql, qr, x);
add(v * 2 + 1, mid, r, ql, qr, x);
tree[v] = min(tree[v * 2], tree[v * 2 + 1]) + m[v];
}
ll find_first(ll l, ll r) {
if (!get(l, r)) {
return r;
}
return find_first(1, 0, size, l, r);
}
ll find_first(ll v, ll l, ll r, ll ql, ll qr) {
if (r - l == 1) {
return l;
}
ll mid = (l + r) / 2;
if (get(v * 2, l, mid, ql, qr)) {
return find_first(v * 2, l, mid, ql, qr);
} else {
return find_first(v * 2 + 1, mid, r, ql, qr);
}
}
};
void solve() {
ll n, r, c;
cin >> r >> c >> n;
ll sx, sy, gx, gy;
cin >> sx >> sy >> gx >> gy;
sx--;
sy--;
gx--;
gy--;
vector<vector<bool>> arr(r, vector<bool>(c, false));
vector<vector<bool>> used(r, vector<bool>(c, false));
vector<segment_tree> dist(r, segment_tree(c));
for (ll i = 0; i < r; i++) {
string s;
cin >> s;
for (ll j = 0; j < c; j++) {
if (s[j] == '.') {
arr[i][j] = true;
}
}
}
vector<pair<ll, ll>> now;
now.emplace_back(sx, sy);
used[sx][sy] = true;
ll na = 0;
segment_tree_am sta(c), sta2(c);
vector<ll> col(c, 0);
for (ll i = 0; i < c; i++) {
sta2.add(i, i + 1, 1);
}
while (true) {
vector<pair<ll, ll>> nu;
vector<vector<pair<ll, ll>>> all(r * 2);
while (!now.empty()) {
auto[x, y] = now.back();
nu.emplace_back(x, y);
if (x == gx && y == gy) {
cout << na << '\n';
return;
}
now.pop_back();
if (x > 0 && arr[x - 1][y]) {
if (!used[x - 1][y]) {
used[x - 1][y] = true;
now.emplace_back(x - 1, y);
}
}
if (x + 1 < r && arr[x + 1][y]) {
if (!used[x + 1][y]) {
used[x + 1][y] = true;
now.emplace_back(x + 1, y);
}
}
if (y > 0 && arr[x][y - 1]) {
if (!used[x][y - 1]) {
used[x][y - 1] = true;
now.emplace_back(x, y - 1);
}
}
if (y + 1 < c && arr[x][y + 1]) {
if (!used[x][y + 1]) {
used[x][y + 1] = true;
now.emplace_back(x, y + 1);
}
}
all[max(x - n + 1, 0ll) * 2].emplace_back(max(y - n, 0ll), min(y + n + 1, c));
all[(min(x + n, r) - 1) * 2 + 1].emplace_back(max(y - n, 0ll), min(y + n + 1, c));
}
na++;
for (auto[x, y] : nu) {
if (x - n >= 0) {
ll i = x - n;
for (auto j : dist[i].set(max(y - n + 1, 0ll), min(y + n, c))) {
if (!used[i][j]) {
used[i][j] = true;
now.emplace_back(i, j);
}
}
}
if (x + n < r) {
ll i = x + n;
for (auto j : dist[i].set(max(y - n + 1, 0ll), min(y + n, c))) {
if (!used[i][j]) {
used[i][j] = true;
now.emplace_back(i, j);
}
}
}
}
for (ll i = 0; i < r; i++) {
for (auto[l, r] : all[i * 2]) {
sta.add(l, r, 1);
if (!col[l]) {
sta2.add(l, l + 1, -1);
}
col[l]++;
}
ll nn = 0;
while (nn < c) {
nn = sta2.find_first(nn, c);
ll en = sta.find_first(nn, c);
for (auto j : dist[i].set(nn, en)) {
if (!used[i][j]) {
used[i][j] = true;
now.emplace_back(i, j);
}
}
nn = en;
}
for (auto[l, r] : all[i * 2 + 1]) {
sta.add(l, r, -1);
col[l]--;
if (!col[l]) {
sta2.add(l, l + 1, 1);
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}