Submission #1254329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254329		bbldrizzy	Walk (CEOI06_walk)	C++20	0 / 100	82 ms	6072 KiB

walk

#include <bits/stdc++.h> 
#include <ios>
#include <iostream>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define f first
#define s second
const ll MOD = 998244353;

ll d(ll x1, ll y1, ll x2, ll y2) {
    return abs(x1-x2) + abs(y1-y2);
}

int main() {
    ll X, Y; cin >> X >> Y;
    int n; cin >> n;
    vector<pair<P, P>> pts;
    vector<P> dp(n+1, {1e9, 1e9});
    dp[0] = {0, 0};
    for (int i = 0; i < n; i++) {
        ll a, b, c, d; cin >> a >> b >> c >> d;
        pts.push_back({{a-1, c+1}, {b-1, d+1}});
        // pts.push_back({c+1, d+1});
        // pts.push_back({c+1, b-1});

    }
    sort(pts.begin(), pts.end());
    // for (auto x: pts) {
    //     cout << x.f.f << ", " << x.f.s << ", " << x.s.f << ", " << x.s.s << "\n";
    // }
    // cout << "\n";
    set<pair<ll, ll>> y;
    y.insert({0, 0}); // <y=k, ith rect>
    for (int i = 0; i < n; i++) {
        // cout << "Y: " << "\n";
        // for (auto it: y) {
        //     cout << it.f << ", " << it.s << "\n";
        // }
        ll x = pts[i].f.f;
        if (x > X) break;
        ll b = pts[i].s.f;
        ll t = pts[i].s.s;
        auto it1 = y.lower_bound({b, 0});
        auto it2 = y.upper_bound({t, 1e9});
        vector<pair<ll, ll>> to_erase;
        vector<pair<ll, ll>> to_insert;
        for (auto it3 = it1; it3 != it2; it3++) {
            pair<ll, ll> tp = (*it3);
            if (tp.s == 0) {
                dp[i+1].f = min(dp[i+1].f, dp[tp.s].f+d(0, 0, x, b));
                dp[i+1].s = min(dp[i+1].s, dp[tp.s].f+d(0, 0, x, t));
                // cout << "b, i+1: " << b << ", " << i+1 << "\n";
                // cout << "t, i+1: " << t << ", " << i+1 << "\n";
                to_insert.push_back({b, i+1});
                to_insert.push_back({t, i+1});
                to_erase.push_back(tp);
            } else {
                ll rect = tp.s-1;
                ll st = pts[rect].f.f;
                ll vl = (tp.f == pts[rect].s.f) ? dp[tp.s].f : dp[tp.s].s;
                dp[i+1].f = min(dp[i+1].f, vl+d(st, tp.f, x, b));
                dp[i+1].s = min(dp[i+1].s, vl+d(st, tp.f, x, t));
                // cout << "b2, i+1: " << b << ", " << i+1 << "\n";
                // cout << "t2, i+1: " << t << ", " << i+1 << "\n";
                to_insert.push_back({b, i+1});
                to_insert.push_back({t, i+1});
                to_erase.push_back(tp);
            }
        }
        for (auto it: to_insert) {
            y.insert(it);
        }
        for (auto it: to_erase) {
            y.erase(it);
        }
    }
    ll mn = 1e9;
    for (auto it: y) {
        // cout << it.f << ", " << dp[it.s].f << ", " << dp[it.s].s << "\n";
        ll vl = (it.f == pts[it.s-1].s.f) ? dp[it.s].f : dp[it.s].s;
        mn = min(mn, vl+d(pts[it.s-1].f.f, it.f, X, Y));
    }
    cout << mn;
}

• Subtask 1: 0 / 100