Submission #548628

#	Time	Username	Problem	Language	Result	Execution time	Memory
548628		Evang	Walk (CEOI06_walk)	C++17	100 / 100	91 ms	22012 KiB

walk

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

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pdb = pair<db, db>;
using pld = pair<ld, ld>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using vpdb = vc<pdb>;
using vpld = vc<pld>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int N = 1e5+5;
int n, dx, dy, a[N], b[N], c[N], d[N], nxt[N][2], g[N][4], ans;
struct segtree {
    int size = 1<<21, tr[(1<<22)+100];
    segtree() {
        memset(tr, -1, sizeof tr);
    }
    void push(int i){
        if(tr[i] == -1) return;
        if(i < size) {
            tr[2 * i] = tr[2 * i + 1] = tr[i];
            tr[i] = -1;
        }
    }
    void set(int l, int r, int i, int il, int ir, int x){
        if(ir < l || r < il)
            return;
        if(l <= il && ir <= r){
            tr[i] = x;
            return;
        }

        push(i);
        int im = (il+ir)/2;
        set(l, r, 2*i, il, im, x);
        set(l, r, 2*i+1, im+1, ir, x);
    }
    void set(int l, int r, int x){
        set(l, r, 1, 0, size-1, x);
    }
    int get(int i){
        int ans=-1;
        i += size;
        while(i>0){
            if(tr[i] != -1)
                ans = tr[i];
            i /= 2;
        }
        return ans;
    }
}seg;
vpi mov;

int dis(int x, int y, int x2, int y2){
    return abs(x-x2) + abs(y-y2);
}

void evan2(int x, int y, int x2, int y2){
    ans += abs(x-x2) + abs(y-y2);
    if(x != x2)
        mov.eb(x2-x, 0);
    if(y!=y2)
        mov.eb(0, y2-y);
    assert(ssize(mov)<=int(1e6));
}

//void evan3(int x, int y, int j){
//    if(j==-1){
//        evan2(0, 1e6+1, x, y);
//        return;
//    }
//
//    int option_down = g[j][2] + dis(c[j], b[j], x, y);
//    int option_up = g[j][3] + dis(c[j], d[j], x, y);
//    if(option_down < option_up){
//        evan3(c[j], b[j], nxt[j][0]);
//        evan2(c[j], b[j], x, y);
//    }else{
//        evan3(c[j], d[j], nxt[j][1]);
//        evan2(c[j], d[j], x, y);
//    }
//}

void evan(int i){
    if(i==-1)
        return;

    int j = nxt[i][0];
    if(j==-1)
        g[i][0] = dis(0, 1e6+1, a[i], b[i]);
    else{
        evan(j);
        g[i][0] = min(g[j][2] + dis(c[j], b[j], a[i], b[i]),
                      g[j][3] + dis(c[j], d[j], a[i], b[i]));
    }

    j = nxt[i][1];
    if(j==-1)
        g[i][1] = dis(0, 1e6+1, a[i], d[i]);
    else{
        if(nxt[i][0] != nxt[i][1])
            evan(j);
        g[i][1] = min(g[j][2] + dis(c[j], b[j], a[i], d[i]),
                      g[j][3] + dis(c[j], d[j], a[i], d[i]));
    }

    g[i][2] = dis(a[i], b[i], c[i], b[i]) + g[i][0];
    g[i][3] = dis(c[i], d[i], a[i], d[i]) + g[i][1];
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> dx >> dy >> n;
    dy += 1e6+1;
    vi cc;
    vpi e{{dx, -1}};
    for(int i = 0; i < n; ++i){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        if(a[i] > c[i])
            swap(a[i], c[i]);
        if(b[i] > d[i])
            swap(b[i], d[i]);
        e.eb(a[i], i);

        --a[i];
        --b[i];
        ++c[i];
        ++d[i];
        b[i] += 1e6+1;
        d[i] += 1e6+1;
    }
    sort(all(e));

    int d_nxt = -1;
    for(auto[x, i]: e){
        if(i==-1){
            d_nxt = seg.get(dy);
            break;
        }

        nxt[i][0] = seg.get(b[i]);
        nxt[i][1] = seg.get(d[i]);
        seg.set(b[i]+1, d[i]-1, i);

        int j = nxt[i][0];
        if(j==-1)
            g[i][0] = dis(0, 1e6+1, a[i], b[i]);
        else{
//            evan(j);
            g[i][0] = min(g[j][2] + dis(c[j], b[j], a[i], b[i]),
                          g[j][3] + dis(c[j], d[j], a[i], b[i]));
        }

        j = nxt[i][1];
        if(j==-1)
            g[i][1] = dis(0, 1e6+1, a[i], d[i]);
        else{
//            if(nxt[i][0] != nxt[i][1])
//                evan(j);
            g[i][1] = min(g[j][2] + dis(c[j], b[j], a[i], d[i]),
                          g[j][3] + dis(c[j], d[j], a[i], d[i]));
        }

        g[i][2] = dis(a[i], b[i], c[i], b[i]) + g[i][0];
        g[i][3] = dis(c[i], d[i], a[i], d[i]) + g[i][1];
    }

//    if(j !=-1)
//        evan(j);

    int x = dx, y = dy;
    int j = d_nxt;
    while(1){
        if(j==-1) {
            evan2(0, 1e6 + 1, x, y);
            break;
        }

        int option_down = g[j][2] + dis(c[j], b[j], x, y);
        int option_up = g[j][3] + dis(c[j], d[j], x, y);
        if(option_down < option_up){
            evan2(c[j], b[j], x, y);
            tie(x, y, j) = mt(c[j], b[j], nxt[j][0]);
        }else{
            evan2(c[j], d[j], x, y);
            tie(x, y, j) = mt(c[j], d[j], nxt[j][1]);
        }
    }

    cout << ans << el;
    cout << ssize(mov) << el;
    reverse(all(mov));
    for(auto[x, y]: mov)
        cout << x << sp << y << el;
}

• Subtask 1: 100 / 100