Submission #1225325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225325		g4yuhg	Walk (CEOI06_walk)	C++20	100 / 100	139 ms	13740 KiB

walk

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 100005
using namespace std;

bool ghuy4g;

ll en_x, en_y, n;
ll d[N][2], st[6 * N], f[6 * N], m;
pii trace[N][2];

map<ll, ll> bit;
ll mx = 2e6 + 5, base = 1e6 + 1;

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

void lazy(ll id) {
	if (f[id] == 0) return;
	st[id] = f[id];
	f[id * 2] = f[id];
	f[id * 2 + 1] = f[id];
	f[id] = 0;
}
void update(ll id, ll l, ll r, ll L, ll R, ll v) {
	lazy(id);
	if (l > R || r < L) return;
	if (L <= l && r <= R) {
		f[id] = v;
		lazy(id);
		return;
	}
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, L, R, v);
	update(id * 2 + 1, mid + 1, r, L, R, v);
	st[id] = st[id * 2] + st[id * 2 + 1];
}
ll get(ll id, ll l, ll r, ll i) {
	lazy(id);
	if (i > r || i < l) return 0;
	if (l == r) return st[id];
	ll mid = (l + r) / 2;
	return get(id * 2, l, mid, i) + get(id * 2 + 1, mid + 1, r, i);
}

vector<ll> nenSo;
ll id(ll i) {
	return lower_bound(nenSo.begin(), nenSo.end(), i) - nenSo.begin() + 1;
}

void upd(ll l, ll r, ll v) {
	update(1, 1, m, id(l), id(r), v);	
}
ll get(ll x) {
	return get(1, 1, m, id(x));
}

struct vuong {
	ll x1, y1, x2, y2;
} p[N];

bool cmp(vuong a, vuong b) {
	return a.x2 < b.x2;
}
vector<pii> res;

void tv(ll xet, ll x, ll y, ll idx, ll tt) {
	// xet la thang tiep theo, lui ve
    res.push_back({x - p[xet].x2 - 1, 0});
    if (trace[idx][tt] == make_pair(xet, 0LL) ) {
    	res.push_back({0, y - (p[xet].y2 + 1)});
    	//cout << "push: y1 " << p[xet].y2 + 1 - y << endl;
    }
    else {
    	res.push_back({0, y - (p[xet].y1 - 1)});
    	//cout << "push: y2 " << y - (p[xet].y1 - 1) << endl;
    }
}

bool klinh;

signed main(void) {
    faster;
    cin >> en_x >> en_y;
    nenSo.push_back(en_y);
	cin >> n;
	    
	for (int i = 1; i <= n; i ++) {
		cin >> p[i].x1 >> p[i].y1 >> p[i].x2 >> p[i].y2;
		nenSo.push_back(p[i].y2);
		nenSo.push_back(p[i].y1);
		nenSo.push_back(p[i].y2 + 1);
		nenSo.push_back(p[i].y1 - 1);
	}    
	
    sort(p + 1, p + 1 + n, cmp);
      
    
    sort(nenSo.begin(), nenSo.end());
    nenSo.resize(unique(nenSo.begin(), nenSo.end()) - nenSo.begin());
    m = nenSo.size();
    
    for (int i = 1; i <= n; i ++) {
    	ll x1 = p[i].x1, x2 = p[i].x2, y1 = p[i].y1, y2 = p[i].y2;
    	//cout << i << " : " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
    	if (x2 > en_x) break;
    	// xet 2 diem 
    	if (1) {
    		ll x = x2 + 1, y = y2 + 1;
    		ll xet = get(y);
    		if (xet == 0) {
    			d[i][0] = dist(0, 0, x, y);
    		}
    		else {
    			ll xet1 = dist(x, y, p[xet].x2 + 1, p[xet].y2 + 1) +d[xet][0];
    			ll xet2 = dist(x, y, p[xet].x2 + 1, p[xet].y1 - 1) +d[xet][1];
    			if (xet1 > xet2) {
    				d[i][0] = xet2;
    				trace[i][0] = {xet, 1};
    			}
    			else {
    				d[i][0] = xet1;
    				trace[i][0] = {xet, 0};
    			}
    		}
    	}
    	if (1) {
    		ll x = x2 + 1, y = y1 - 1;
    		ll xet = get(y);
    		if (xet == 0) {
    			d[i][1] = dist(0, 0, x, y);
    		}
    		else {
    			ll xet1 = dist(x, y, p[xet].x2 + 1, p[xet].y2 + 1) +d[xet][0];
    			ll xet2 = dist(x, y, p[xet].x2 + 1, p[xet].y1 - 1) +d[xet][1];
    			if (xet1 > xet2) {
    				d[i][1] = xet2;
    				trace[i][1] = {xet, 1};
    			}
    			else {
    				d[i][1] = xet1;
    				trace[i][1] = {xet, 0};
    			}
    		}
    	}
    	upd(y1, y2, i);
    }
    
    ll xet = get(en_y);
    //cout << "xet: " << xet << endl;
    if (xet == 0) {
    	cout << dist(0, 0, en_x, en_y) << endl;
    	//return 0;
    	cout << 2 << endl;
    	cout << en_y << " " << 0 << endl;
    	cout << 0 << " " << en_x << endl;
    }
    else {
    	ll xet1 = dist(en_x, en_y, p[xet].x2 + 1, p[xet].y2 + 1) + d[xet][0];
    	ll xet2 = dist(en_x, en_y, p[xet].x2 + 1, p[xet].y1 - 1) + d[xet][1];
    	cout << min(xet1, xet2) << endl;
    	ll cur = xet;
    	pii ht, ht1;
    	res.push_back({en_x - p[xet].x2 - 1, 0});
    	if (xet1 < xet2) {
    		res.push_back({0, en_y - (p[xet].y2 + 1)});
    		ht = {p[xet].x2 + 1, p[xet].y2 + 1};
    		ht1 = {xet, 0};
    	}
    	else {
    		res.push_back({0, en_y - (p[xet].y1 - 1)});
    		ht = {p[xet].x2 + 1, p[xet].y1 - 1};
    		ht1 = {xet, 1};
    	}
    	while (true) {
    		//cout << ht.fi << " " << ht.se << " " << ht1.fi << " " << ht1.se << endl; // ht1 la luu chi so, ht la luu x y
    		if (trace[ht1.fi][ht1.se] == make_pair(0LL, 0LL)) {
    			res.push_back({ht.fi - 0, 0});
    			res.push_back({0, ht.se - 0});
    			break;
    		}
    		tv(trace[ht1.fi][ht1.se].fi, ht.fi, ht.se, ht1.fi, ht1.se);
    		ht1 = trace[ht1.fi][ht1.se];
    		if (ht1.se == 0) {
    			ht.fi = p[ht1.fi].x2 + 1, ht.se = p[ht1.fi].y2 + 1;
    		}
    		else {
    			ht.fi = p[ht1.fi].x2 + 1, ht.se = p[ht1.fi].y1 - 1;
    		}
    		
    	}
    	cout << res.size() << endl;
    	for (int i = res.size() - 1; i >= 0; i --) {
    		cout << res[i].fi << " " << res[i].se << endl;
    	}
    }
    
    
    cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
    return 0;
}

• Subtask 1: 100 / 100