Submission #771832

#	Time	Username	Problem	Language	Result	Execution time	Memory
771832		green_gold_dog	Maze (JOI23_ho_t3)	C++17	86 / 100	2060 ms	89648 KiB

Main

#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;
        segment_tree_am sta(c);
        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);
                                        }
                                }
                        }
                }
                multiset<ll> nnn;
                nnn.insert(c);
                for (ll i = 0; i < r; i++) {
                        for (auto[l, r] : all[i * 2]) {
                                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();
}

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