Submission #404188

#	Time	Username	Problem	Language	Result	Execution time	Memory
404188		timmyfeng	Golf (JOI17_golf)	C++17	100 / 100	5971 ms	916852 KiB

golf

#include <bits/stdc++.h>
using namespace std;

const int M = 1000000007;

struct segtree {
    segtree *left = nullptr, *right = nullptr;
    map<int, array<int, 2>> lines;

    void update(int a, int b, int x, int l, int r) {
        if (a <= l && r <= b) {
            lines[x] = {a, b};
        } else {
            int m = (l + r) / 2;

            if (a <= m) {
                if (!left) {
                    left = new segtree();
                }
                left->update(a, b, x, l, m);
            }

            if (b > m) {
                if (!right) {
                    right = new segtree();
                }
                right->update(a, b, x, m + 1, r);
            }
        }
    }

    void query(int x, int a, int b, vector<array<int, 3>> &out, int l, int r) {
        auto begin = lines.lower_bound(a), end = begin;
        while (end != lines.end() && end->first <= b) {
            out.push_back({end->first, end->second[0], end->second[1]});
            ++end;
        }
        lines.erase(begin, end);

        int m = (l + r) / 2;
        if (x <= m) {
            if (left) {
                left->query(x, a, b, out, l, m);
            }
        } else {
            if (right) {
                right->query(x, a, b, out, m + 1, r);
            }
        }
    }
};

vector<array<int, 3>> events[2];
set<array<int, 3>> visited[2];
segtree *nodes[2];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int xs, ys, xt, yt;
    cin >> xs >> ys >> xt >> yt;

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        int x1, x2, y1, y2;
        cin >> x1 >> x2 >> y1 >> y2;

        for (auto x : {x1, x2}) {
            events[0].push_back({y1, 1, x});
            events[0].push_back({y2, -1, x});

            events[1].push_back({x, 0, y1});
        }

        for (auto y : {y1, y2}) {
            events[1].push_back({x1, 1, y});
            events[1].push_back({x2, -1, y});

            events[0].push_back({y, 0, x1});
        }
    }

    events[0].push_back({ys, 0, xs});
    events[0].push_back({yt, 0, xt});
    events[1].push_back({xs, 0, ys});
    events[1].push_back({xt, 0, yt});

    for (int k = 0; k < 2; ++k) {
        sort(events[k].begin(), events[k].end());
        nodes[k] = new segtree();
        set<int> walls = {0, M};

        for (auto [a, t, b] : events[k]) {
            if (t == -1) {
                walls.erase(b);
            } else if (t == 1) {
                walls.insert(b);
            } else {
                auto it = walls.lower_bound(b);
                int r = *it, l = *(--it);
                nodes[k]->update(l, r, a, 0, M);
            }
        }
    }

    vector<array<int, 3>> init;
    nodes[0]->query(xs, ys, ys, init, 0, M);
    nodes[1]->query(ys, xs, xs, init, 0, M);

    queue<array<int, 5>> bfs;
    for (int k = 0; k < 2; ++k) {
        bfs.push({1, k, init[k][0], init[k][1], init[k][2]});
        visited[k].insert(init[k]);
    }

    while (!bfs.empty()) {
        auto [dist, o, a, b, c] = bfs.front();
        bfs.pop();

        if ((o == 0 && a == yt && b <= xt && xt <= c) ||
            (o == 1 && a == xt && b <= yt && yt <= c)) {
            cout << dist << "\n";
            exit(0);
        }

        vector<array<int, 3>> adj;
        nodes[1 - o]->query(a, b, c, adj, 0, M);

        for (auto [d, e, f] : adj) {
            if (visited[1 - o].count({d, e, f}) == 0) {
                bfs.push({dist + 1, 1 - o, d, e, f});
                visited[1 - o].insert({d, e, f});
            }
        }
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70