#include<bits/stdc++.h>
using namespace std;
typedef long long 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;
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);
}
}
}
}
segment_tree_am sta(c);
multiset<ll> nnn;
nnn.insert(c);
for (ll i = 0; i < r; i++) {
for (auto[l, r] : all[i * 2]) {
for (auto j : dist[i].set(l, r)) {
if (!used[i][j]) {
used[i][j] = true;
now.emplace_back(i, j);
}
}
//sta.add(l, r, 1);
//nnn.insert(l);
}
//ll nn = 0;
//while (nn < c) {
// nn = *nnn.lower_bound(nn);
// 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);
// nnn.erase(nnn.find(l));
//}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
320 KB |
Output is correct |
| 8 |
Correct |
3 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
320 KB |
Output is correct |
| 11 |
Correct |
1 ms |
320 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
320 KB |
Output is correct |
| 15 |
Correct |
1 ms |
316 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
18 ms |
468 KB |
Output is correct |
| 20 |
Execution timed out |
2095 ms |
2896 KB |
Time limit exceeded |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
320 KB |
Output is correct |
| 8 |
Correct |
3 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
320 KB |
Output is correct |
| 11 |
Correct |
1 ms |
320 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
320 KB |
Output is correct |
| 15 |
Correct |
1 ms |
316 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
18 ms |
468 KB |
Output is correct |
| 20 |
Execution timed out |
2095 ms |
2896 KB |
Time limit exceeded |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
320 KB |
Output is correct |
| 8 |
Correct |
3 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
320 KB |
Output is correct |
| 11 |
Correct |
1 ms |
320 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
320 KB |
Output is correct |
| 15 |
Correct |
1 ms |
316 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
18 ms |
468 KB |
Output is correct |
| 20 |
Execution timed out |
2095 ms |
2896 KB |
Time limit exceeded |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
320 KB |
Output is correct |
| 8 |
Correct |
3 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
320 KB |
Output is correct |
| 11 |
Correct |
1 ms |
320 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
320 KB |
Output is correct |
| 15 |
Correct |
1 ms |
316 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
18 ms |
468 KB |
Output is correct |
| 20 |
Execution timed out |
2095 ms |
2896 KB |
Time limit exceeded |
| 21 |
Halted |
0 ms |
0 KB |
- |
