Submission #1208870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208870		urejgi	Walk (CEOI06_walk)	C++17	30 / 100	107 ms	16900 KiB

walk

#pragma GCC optimize("O3,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

constexpr int N = 1e5+1, L = 1 << 20;

struct S{ int x[2], y[2], i; };

S r[N];
int tr[L<<1], d[N][2], g[N][2];
bitset<N> pre[2];

inline void upd(int x, int i){
    tr[x += L] = i;
    while(x >>= 1) tr[x] = tr[x<<1|1] != -1 ? tr[x<<1|1] : tr[x<<1];
}

inline int get(int j){
    j += L;
    int u = -1, v = -1, i = L;
    while(i <= j){
        if(i&1) u = tr[i] != -1 ? tr[i] : u, i++;
        if(!(j&1)) v = v==-1 ? tr[j] : v, --j;
        i >>= 1;
        j >>= 1;
    }
    return v != -1 ? v : u;
}

inline int dist(int i, bool tpi, int j, bool tpj){
    return abs(r[i].x[tpi] + (tpi ? 1 : -1) - r[j].x[tpj] - (tpj ? 1 : -1)) +
           abs(r[i].y[tpi] + (tpi ? 1 : -1) - r[j].y[tpj] - (tpj ? 1 : -1));
}

inline int path(int i, bool tp){
    if(d[i][tp]) return d[i][tp];
    if(g[i][tp] == -1) 
        return d[i][tp] = r[i].x[tp] + (tp ? 1 : -1) + abs(r[i].y[tp] + (tp ? 1 : -1));
    int d1 = dist(i, tp, g[i][tp], 0) + path(g[i][tp], 0);
    int d2 = dist(i, tp, g[i][tp], 1) + path(g[i][tp], 1);
    pre[i][tp] = d2 < d1;
    return d[i][tp] = min(d1,d2);
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int x,y; cin >> x >> y;
    int n; cin >> n;
    vector<tuple<int,int,int>> evs;
    for(int i = 0; i < n; i++){
        cin >> r[i].x[0] >> r[i].y[0] >> r[i].x[1] >> r[i].y[1];
        evs.emplace_back(r[i].y[0], 0, i);
        evs.emplace_back(r[i].y[0]-1, 1, i);
        evs.emplace_back(r[i].y[1]+1, 2, i);
        evs.emplace_back(r[i].y[1], 3, i);
    }
    r[n].x[0] = r[n].x[1] = x+1, r[n].y[0] = r[n].y[1] = y+1, r[n].i = n;
    evs.emplace_back(r[n].y[0]-1, 1, n);
    sort(evs.begin(), evs.end());
    memset(tr, 255, sizeof(tr));
    for(const auto&[_y, tp, i]:evs){
        if(!tp) upd(r[i].x[1], i);
        else if(tp == 1) g[i][0] = get(r[i].x[0]-1);
        else if(tp == 2) g[i][1] = get(r[i].x[0]-1);
        else upd(r[i].x[1], -1);
    }
    cout << path(n, 0) << '\n';
    int i = n;
    bool tp = 0;
    vector<pair<int,int>> path;
    auto add_pt = [&path](int x, int y){
        if (path.size() >= 2 && ((x == path.back().first 
            && path.back().first == (++path.rbegin())->first) 
                || (y == path.back().second && path.back().second 
                    == (++path.rbegin())->second))) path.pop_back();
                    
        path.emplace_back(x,y);
    };
    while(g[i][tp] != -1){
        int j = g[i][tp];
        bool nxt = pre[i][tp];
        add_pt(r[i].x[tp] + (tp ? 1 : -1), r[i].y[tp] + (tp ? 1 : -1));
        add_pt(r[j].x[1] + 1, r[i].y[tp] + (tp ? 1 : -1));
        if(!nxt) add_pt(r[j].x[1] + 1, r[j].y[0]-1);
        i = j;
        tp = nxt;
    }
    add_pt(r[i].x[tp] + (tp ? 1 : -1), r[i].y[tp] + (tp ? 1 : -1));
    add_pt(0, r[i].y[tp] + (tp ? 1 : -1));
    add_pt(0, 0);
    reverse(path.begin(), path.end());
    cout << path.size()-1 << '\n';
    for(int i = 1; i < path.size(); i++) 
        cout << path[i].first - path[i-1].first 
                << ' ' << path[i].second - path[i-1].second << '\n';
    return 0;
}

• Subtask 1: 30 / 100