Submission #1265871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265871		huyjavalt	Walk (CEOI06_walk)	C++20	100 / 100	137 ms	38656 KiB

walk

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

#define double long double
#define int long long

struct Line{
    int x,l,r,i,t;
    // t = 0 -> left side
    // t = 2 -> right side
    // t = 1 -> query;

    bool operator<(const Line& other) const{
        if(x == other.x) return t > other.t;
        return x < other.x;
    }
};

vector<Line> ev;
int t[9000005];
int lazy[9000005];

void push(int v, int tl, int tr){
    if(lazy[v]){
        t[v] = lazy[v];
        if(tl != tr){
            lazy[v*2] = lazy[v];
            lazy[v*2+1] = lazy[v];
        }
        lazy[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, int x){
    push(v,tl,tr);
    if(l > tr || r < tl) return;
    if(l <= tl && tr <= r){
        lazy[v] = x;
        push(v,tl,tr);
        return;
    }
    int tm = (tl+tr)/2;
    update(v*2,tl,tm,l,r,x);
    update(v*2+1,tm+1,tr,l,r,x);
}

int query(int v, int tl, int tr, int pos){
    push(v,tl,tr);
    if(tl == tr) return t[v];
    int tm = (tl+tr)/2;
    if(pos <= tm) return query(v*2,tl,tm,pos);
    return query(v*2+1,tm+1,tr,pos);
}

pair<int,int> node[500005];
vector<int> adj[500005];
int dp[500005];
int deg[500005];
int pre[500005];

int add = 1e6+1;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("squares.in","r",stdin);
//    freopen("squares.out","w",stdout);
    int dx,dy;
    cin >> dx >> dy;
    int n;
    cin >> n;

    int cnt = 0;
    node[++cnt] = {0,add};

    for(int i = 1; i <= n; i++){
        int x,y,u,v;
        cin >> x >> y >> u >> v;
        y += add, v += add;

        ev.push_back({u+1,y-1,y-1,++cnt,1}), node[cnt] = {u+1,y-1};
        ev.push_back({u+1,v+1,v+1,++cnt,1}), node[cnt] = {u+1,v+1};
        ev.push_back({u,y,v,i,0});
    }
    dy += add;

    ev.push_back({dx,dy,dy,++cnt,1}), node[cnt] = {dx,dy};
    sort(ev.begin(), ev.end());

    for(auto &p : ev){
        //cout << p.l << ' ' << p.r << ' ' << p.t << ' ' << p.i << endl;
        if(p.t == 0) update(1,0,2e6+2,p.l,p.r,p.i);
        else{
            int par = query(1,0,2e6+2,p.l);
            if(par){
                adj[par*2].push_back(p.i);
                adj[par*2+1].push_back(p.i);
                deg[p.i] += 2;

                //cout << par*2 << ' ' << par*2+1 << ' ' << p.i << endl;
            }else{
                adj[1].push_back(p.i), deg[p.i]++;
                //cout << 1 << ' ' << p.i << endl;
            }
        }
    }

    queue<int> q;
    for(int i = 1; i <= cnt; i++) dp[i] = 1e18;
    dp[1] = 0;
    q.push(1);
    while(q.size()){
        int i = q.front(); q.pop();
        for(auto j : adj[i]){
            int c = dp[i]+abs(node[i].first - node[j].first)+abs(node[i].second - node[j].second);
            if(dp[j] > c){
                dp[j] = c;
                pre[j] = i;
            }
            if(--deg[j] == 0) q.push(j);
        }
    }

    cout << dp[cnt] << '\n';
    vector<pair<int,int>> res;
    int d = cnt;
    while(d != 1){
        int p = pre[d];
        if(node[d].first - node[p].first) res.push_back({node[d].first - node[p].first,0});
        if(node[d].second - node[p].second) res.push_back({0,node[d].second - node[p].second});
        d = p;
    }

    cout << res.size() << '\n';
    reverse(res.begin(), res.end());
    for(auto p : res) cout << p.first << ' ' << p.second << '\n';
    return 0;
}

• Subtask 1: 100 / 100