Submission #854377

#	Time	Username	Problem	Language	Result	Execution time	Memory
854377		arbuzick	Maze (JOI23_ho_t3)	C++17	43 / 100	2070 ms	638248 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

constexpr int R = 1 << 12;

set<pair<int, int>> tree[R * 2];

void add(int pos, pair<int, int> val) {
    for (pos += R; pos > 0; pos /= 2) {
        tree[pos].insert(val);
    }
}

void del(int pos, pair<int, int> val) {
    for (pos += R; pos > 0; pos /= 2) {
        tree[pos].erase(val);
    }
}

pair<int, int> get_val(int l, int r, int x, int y) {
    l = max(l, 0);
    r = min(r, R);
    l += R;
    r += R;
    pair<int, int> ans = {-1, -1};
    while (l < r) {
        if (l & 1) {
            auto it = tree[l].lower_bound({x, 0});
            if (it != tree[l].end() && x <= it->first && it->first < y) {
                return *it;
            }
            l++;
        }
        if (r & 1) {
            --r;
            auto it = tree[r].lower_bound({x, 0});
            if (it != tree[r].end() && x <= it->first && it->first < y) {
                return *it;
            }
        }
        l >>= 1;
        r >>= 1;
    }
    return ans;
}

void solve() {
    int r, c, n;
    cin >> r >> c >> n;
    int sx, sy;
    cin >> sx >> sy;
    sx--, sy--;
    int gx, gy;
    cin >> gx >> gy;
    gx--, gy--;
    vector<string> a(r);
    for (int i = 0; i < r; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            add(i, {j, i});
        }
    }
    vector<vector<int>> dp(r, vector<int>(c, r * c));
    deque<pair<int, int>> dq;
    dp[sx][sy] = 0;
    del(sx, {sy, sx});
    dq.push_back({sx, sy});
    while (!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        if (x > 0 && a[x - 1][y] == '.' && dp[x - 1][y] > dp[x][y]) {
            if (dp[x - 1][y] == r * c) {
                del(x - 1, {y, x - 1});
            }
            dp[x - 1][y] = dp[x][y];
            dq.push_front({x - 1, y});
        }
        if (x + 1 < r && a[x + 1][y] == '.' && dp[x + 1][y] > dp[x][y]) {
            if (dp[x + 1][y] == r * c) {
                del(x + 1, {y, x + 1});
            }
            dp[x + 1][y] = dp[x][y];
            dq.push_front({x + 1, y});
        }
        if (y > 0 && a[x][y - 1] == '.' && dp[x][y - 1] > dp[x][y]) {
            if (dp[x][y - 1] == r * c) {
                del(x, {y - 1, x});
            }
            dp[x][y - 1] = dp[x][y];
            dq.push_front({x, y - 1});
        }
        if (y + 1 < c && a[x][y + 1] == '.' && dp[x][y + 1] > dp[x][y]) {
            if (dp[x][y + 1] == r * c) {
                del(x, {y + 1, x});
            }
            dp[x][y + 1] = dp[x][y];
            dq.push_front({x, y + 1});
        }
        while (true) {
            auto p = get_val(x - n + 1, x + n, y - n, y + n + 1);
            if (p.first == -1) {
                p = get_val(x - n, x + n + 1, y - n + 1, y + n);
                if (p.first == -1) {
                    break;
                }
            }
            del(p.second, p);
            swap(p.first, p.second);
            dp[p.first][p.second] = dp[x][y] + 1;
            dq.push_back(p);
        }
    }
    cout << dp[gx][gy] << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6