Submission #987698

#	Time	Username	Problem	Language	Result	Execution time	Memory
987698		Double_Slash	Walk (CEOI06_walk)	C++17	100 / 100	411 ms	77704 KiB

walk

#include <bits/stdc++.h>
#define debug(x) [&] { auto _x = x; cerr << __LINE__ << ": " << #x << " = " << _x << endl; }()
 
using namespace std;
using ll = long long;
using pint = pair<int, int>;
#define all(x) x.begin(), x.end()
 
const int MAX = 1e6;
const ll INF = 1e18;
 
struct Val {
    ll dist = INF;
    int x, y;
 
    bool operator<(const Val &o) const { return dist < o.dist; }
};
 
struct Node {
    int l, r;
    Val val;
    bool lazy = false;
    Node *lc, *rc;
 
    Node(int l, int r, const vector<int> &arr) : l(l), r(r) {
        if (l < r) {
            int m = l + ((r - l) >> 1);
            lc = new Node{l, m, arr};
            rc = new Node{m + 1, r, arr};
        }
        this->l = arr[l], this->r = arr[r];
    }
 
    void clean() {
        if (lazy) {
            val.dist = INF;
            if (l < r) lc->lazy = rc->lazy = lazy;
            lazy = false;
        }
    }
 
    Val query(int ql, int qr) {
        if (ql > r or qr < l) return {};
        clean();
        if (l >= ql and r <= qr) return val;
        return min(lc->query(ql, qr), rc->query(ql, qr));
    }
 
    void update(int i, const Val &v) {
        clean();
        if (i < l or i > r) return;
        if (l == r) {
            val = v;
            return;
        }
        lc->update(i, v);
        rc->update(i, v);
        val = min(lc->val, rc->val);
    }
 
    void clear(int ul, int ur) {
        clean();
        if (ul > r or ur < l) return;
        if (l >= ul and r <= ur) {
            lazy = true;
            clean();
            return;
        }
        lc->clear(ul, ur);
        rc->clear(ul, ur);
        val = min(lc->val, rc->val);
    }
};
int X, Y, n;
vector<pint> s[MAX + 1], e[MAX + 1];
map<pint, pint> pre;
 
int main() {
    cin >> X >> Y >> n;
    vector<int> arr{{0}};
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        s[x1].emplace_back(y1, y2);
        e[x2].emplace_back(y1, y2);
        arr.emplace_back(y1 - 1), arr.emplace_back(y2 + 1);
    }
    sort(all(arr));
    arr.erase(unique(all(arr)), arr.end());
    Node *up = new Node{0, (int) arr.size() - 1, arr}, *down = new Node{0, (int) arr.size() - 1, arr};
    up->update(0, {0, 0, 0}), down->update(0, {0, 0, 0});
    map<int, int> blocks;
    blocks[-MAX - 2] = -MAX - 2;
    blocks[MAX + 2] = MAX + 2;
    auto dp = [&] (int y) {
        auto it = blocks.upper_bound(y);
        auto a = up->query(prev(it)->second + 1, y), b = down->query(y, it->first - 1);
        a.dist += y, b.dist -= y;
        return min(a, b);
    };
    for (int x = 0; x <= X; ++x) {
        vector<pint> points;
        for (auto [l, r]: s[x]) points.emplace_back(l - 1, 0), points.emplace_back(r + 1, 0);
        sort(all(points));
        points.erase(unique(all(points)), points.end());
        for (auto &[y, v]: points) {
            auto a = dp(y);
            pre[{x - 1, y}] = {a.x, a.y};
            v = a.dist;
        }
        for (auto [y, v]: points) {
            up->update(y, {v - y, x - 1, y});
            down->update(y, {v + y, x - 1, y});
        }
        for (auto [l, r]: e[x - 1]) blocks.erase(l);
        for (auto [l, r]: s[x]) {
            up->clear(l, r);
            down->clear(l, r);
            blocks[l] = r;
        }
    }
    auto a = dp(Y);
    cout << a.dist + X << endl;
    pre[{X, Y}] = {a.x, a.y};
    vector<pint> coords{{X, Y}};
    while (X or Y) {
        tie(X, Y) = pre[{X, Y}];
        coords.emplace_back(X, Y);
    }
    vector<pint> ans;
    while (coords.size() >= 2) {
        if (coords.end()[-2].first != coords.back().first) {
            if (ans.empty() or ans.back().second) ans.emplace_back(coords.end()[-2].first - coords.back().first, 0);
            else ans.back().first += coords.end()[-2].first - coords.back().first;
        }
        if (coords.end()[-2].second != coords.back().second) {
            if (ans.empty() or ans.back().first) ans.emplace_back(0, coords.end()[-2].second - coords.back().second);
            else ans.back().second += coords.end()[-2].second - coords.back().second;
        }
        coords.pop_back();
    }
    cout << ans.size() << endl;
    for (auto [x, y]: ans) cout << x << " " << y << endl;
}

• Subtask 1: 100 / 100