Submission #1114777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114777		PVSekhar	Walk (CEOI06_walk)	C++14	0 / 100	1077 ms	9800 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 (near.second != p.x) par[p] = Pt(near.second, near.first);
    else par[p] = par[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;
    // cout << p.x << " " << p.y << " l: " << l.first << " " << l.second << " r: " << r.first << " " << r.second << "\n";
    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));
    // pair<int, int> pa = make_pair(p.y, p.x);
    // while (it != store.begin() && *(--it) != pa) {
    //     store.erase(*it);
    // }
}

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));
    }
    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;
    // deque<pair<int, int>> dir;
    // prev = Pt(0, 0);
    // st.pop();
    // while (!st.empty()) {
    //     dest = st.top();
    //     // cout << dest.x << " " << dest.y << " " << prev.x << " " << prev.y << "\n";
    //     ans.push_back(make_pair(dest.x - prev.x, 0ll));
    //     ans.push_back(make_pair(0ll, dest.y - prev.y));
    //     st.pop();
    //     prev = dest;
    // }
    // dir.push_back(ans[0]); 
    // for (int i = 0; i + 1 < ans.size(); i += 2) {
    //     if (ans[i] != make_pair(0, 0)) {
    //         dir.push_back(ans[i + 1]);
    //     } else {
    //         dir.pop_back();
    //         if (dir.empty()) dir.push_back(ans[i + 1]);
    //         else dir.back().second += ans[i + 1].second;
    //     }
    //     if (i + 2 < ans.size()) dir.push_back(ans[i + 2]);
    // }
    // if (dir.back() == make_pair(0, 0)) dir.pop_back();
    // cout << dir.size() << "\n";
    // while (!dir.empty()) {
    //     cout << dir.front().first << " " << dir.front().second << "\n";
    //     dir.pop_front();
    // }
}

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: 0 / 100