Submission #1115246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115246		PVSekhar	Walk (CEOI06_walk)	C++17	84 / 100	1069 ms	25548 KiB

walk

#include <bits/stdc++.h>
using namespace std; 
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 1e6 + 2;
const int INF = 2e6 + 2;

// from jiangly's template
const double TOL = 1e-9;

template<class T>
struct Point {
    T x;
    T y;
    Point(const T x_ = 0, const T y_ = 0) : x(x_), y(y_) {}


    template<class U>
    operator Point<U>() {
        return Point<U>(U(x), U(y));
    }
    Point &operator+=(const Point &p) & {
        x += p.x;
        y += p.y;
        return *this;
    }
    Point &operator-=(const Point &p) & {
        x -= p.x;
        y -= p.y;
        return *this;
    }
    Point &operator*=(const T &v) & {
        x *= v;
        y *= v;
        return *this;
    }
    Point &operator/=(const T &v) & {
        x /= v;
        y /= v;
        return *this;
    }
    Point operator-() const {
        return Point(-x, -y);
    }
    friend Point operator+(Point a, const Point &b) {
        return a += b;
    }
    friend Point operator-(Point a, const Point &b) {
        return a -= b;
    }
    friend Point operator*(Point a, const T &b) {
        return a *= b;
    }
    friend Point operator/(Point a, const T &b) {
        return a /= b;
    }
    friend Point operator*(const T &a, Point b) {
        return b *= a;
    }
    // w/o tolerance
    // friend bool operator<(const Point &a, const Point &b) {
    //     return a.x < b.x || (a.x == b.x && a.y < b.y);
    // }
    // w/ tolerance
    friend bool operator<(const Point &a, const Point &b) {
        return (a.x < b.x || (abs(a.x - b.x) < TOL && a.y < b.y));
    }
    friend bool operator>(const Point &a, const Point &b) {
        return !(a < b);
    }
    // without tolerance
    friend bool operator==(const Point &a, const Point &b) {
        return a.x == b.x && a.y == b.y;
    }
    friend bool operator!=(const Point &a, const Point &b) {
        return !(a.x == b.x && a.y == b.y);
    }
    friend bool operator<=(const Point &a, const Point &b) {
        return a < b || a == b;
    }
    friend bool operator>=(const Point &a, const Point &b) {
        return a > b || a == b;
    }

    // with tolerance
    // friend bool operator==(const Point &a, const Point &b) {
    //     Point<T> p = a - b;
    //     T len = sqrt(p.x * p.x + p.y * p.y);
    //     return len < TOL;
    // }
    // friend bool operator!=(const Point &a, const Point &b) {
    //     Point<T> p = a - b;
    //     T len = sqrt(p.x * p.x + p.y * p.y);
    //     return !(len < TOL);
    // }
    friend std::istream &operator>>(std::istream &is, Point &p) {
        return is >> p.x >> p.y;
    }
    friend std::ostream &operator<<(std::ostream &os, const Point &p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};

using Pt = Point<int>;

int cur_x = 0, x, y, n;
vector<Pt> pts;
map<Pt, Pt> par; // x, y
map<Pt, ll> dis; // x, y
set<pair<int, int>> store; // y, x

void update(Pt &p, pair<int, int> &near) {
    if (near.first == p.y && store.find(near) != store.end()) store.erase(near);
    if (p == Pt(near.second, near.first)) return;
    par[p] = Pt(near.second, near.first);
}

void solve(Pt &p) {
    pair<int, int> l = make_pair(-1, -1), r = make_pair(-1, -1);
    auto it = store.end();
    it = upper_bound(store.begin(), store.end(), make_pair(p.y, INF));
    if (it != store.begin()) l = *(--it);
    it = upper_bound(store.begin(), store.end(), make_pair(p.y, -1));
    if (it != store.end()) r = *it;
    if (l.first == -1) {
        dis[p] = dis[Pt(r.second, r.first)] + abs(p.y - r.first);
        update(p, r);
    } else if (r.first == -1) {
        dis[p] = dis[Pt(l.second, l.first)] + abs(p.y - l.first);
        update(p, l);
    } else {
        ll d1 = dis[Pt(l.second, l.first)] + abs(p.y - l.first), d2 = dis[Pt(r.second, r.first)] + abs(p.y - r.first);
        if (d1 <= d2) {
            dis[p] = d1;
            update(p, l);
        } else {
            dis[p] = d2;
            update(p, r);
        }
    }
    store.insert(make_pair(p.y, p.x));
}

void solve(Pt &p, Pt &q) {
    solve(p);
    solve(q);
    auto it = store.find(make_pair(q.y, q.x));
    if (it == store.end()) {
        return;
    }
    pair<int, int> pa = make_pair(p.y, p.x);
    vector<pair<int, int>> temp;
    while (it != store.begin() && *(--it) != pa) {
        temp.push_back(*it);
    }
    for (auto x : temp) store.erase(x);
}

void solve() {
    ll x1, y1, x2, y2;
    cin >> x >> y >> n;
    y += N;
    for (int i = 0; i < n; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        y1 += N;
        y2 += N;
        pts.push_back(Pt(x1 - 1, y1 - 1));
        pts.push_back(Pt(x1 - 1, y2 + 1));
    }
    pts.push_back(Pt(x, y));
    sort(pts.begin(), pts.end());
    store.insert(make_pair(N, 0));
    dis[Pt(0, N)] = 0;
    for (int i = 0; i < 2 * n; i += 2) {
        if (pts[i].x == x) break;
        solve(pts[i], pts[i + 1]);
    }
    Pt dest = Pt(x, y), prev;
    solve(dest);
    cout << dis[dest] + x << "\n";
    stack<Pt> st;
    st.push(Pt(dest.x, dest.y - N));
    while (dest != Pt(0, N)) {
        dest = par[dest];
        st.push(Pt(dest.x, dest.y - N));
    }
    vector<pair<int, int>> ans;
    prev = st.top();
    st.pop();
    while (!st.empty()) {
        dest = st.top();
        if (dest != prev) {
            if (dest.x != prev.x) {
                if (ans.size() && ans.back().second == 0) ans.back().first += dest.x - prev.x;
                else ans.push_back(make_pair(dest.x - prev.x, 0));
            }
            if (ans.size() && ans.back().first == 0) ans.back().second += dest.y - prev.y;
            else ans.push_back(make_pair(0, dest.y - prev.y));
        }
        prev = dest;
        st.pop();
    }
    cout << ans.size() << "\n";
    for (auto x : ans) {
        cout << x.first << " " << x.second << "\n";
    }
}

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

• Subtask 1: 84 / 100