Submission #1225274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225274		g4yuhg	Walk (CEOI06_walk)	C++20	0 / 100	128 ms	10380 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;

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;
}

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, y = y2 + 1;
    		ll xet = get(y);
    		if (xet == 0) {
    			d[i][0] = dist(0, 0, x, y);
    		}
    		else {
    			d[i][0] = min(dist(x, y, p[xet].x2, p[xet].y2 + 1) +d[xet][0], dist(x, y, p[xet].x2, p[xet].y1 - 1) +d[xet][1]);
    		}
    	}
    	if (1) {
    		ll x = x2, y = y1 - 1;
    		ll xet = get(y);
    		if (xet == 0) {
    			d[i][1] = dist(0, 0, x, y);
    		}
    		else {
    			d[i][1] = min(dist(x, y, p[xet].x2, p[xet].y2 + 1) +d[xet][0], dist(x, y, p[xet].x2, p[xet].y1 - 1) +d[xet][1]);
    		}
    	}
    	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 << 0 << " " << en_x << endl;
    	cout << en_y << " " << 0 << endl;
    }
    else {
    	cout << min(dist(en_x, en_y, p[xet].x2, p[xet].y2 + 1) + d[xet][0], 
    		dist(en_x, en_y, p[xet].x2, p[xet].y1 - 1) + d[xet][1]) << endl;
    	
    }
    
    
    cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
    return 0;
}

• Subtask 1: 0 / 100