Submission #412744

#	Time	Username	Problem	Language	Result	Execution time	Memory
412744		pure_mem	Walk (CEOI06_walk)	C++14	0 / 100	156 ms	12788 KiB

walk

#include <bits/stdc++.h>
 
#define ll long long
#define X first
#define Y second
#define MP make_pair
#define double long double
 
using namespace std;
 
const int N = 1e5 + 12, INF = 1e6 + 2;

int cf(int x, int y);

struct node{
	int p = 0;
	node* to[2] = {nullptr, nullptr}; 
	node* getp(int v){
		if(to[v] == nullptr) to[v] = new node();
		return to[v];
	}
	void upd(int tl, int tr, int l, int r, int val){
		if(tl > r || l > tr) return;
		if(tl >= l && tr <= r) return void(p = val);
		int tm = (tl + tr) / 2;
		if((tl + tr) % 2 == -1) tm -= 1;
		getp(0)->upd(tl, tm, l, r, val);
		getp(1)->upd(tm + 1, tr, l, r, val);
	}
	int get(int tl, int tr, int pos){
		if(tl == tr) return p;
		int tm = (tl + tr) / 2;
		if((tl + tr) % 2 == -1) tm -= 1;
		int val;
		if(pos <= tm) val = (to[0] ? to[0]->get(tl, tm, pos): 0);
		else val = (to[1] ? to[1]->get(tm + 1, tr, pos): 0);
		return cf(val, p);
	}
}root;

int n, nxt[2][N + 1], sx, sy, ans[2][N + 1];
pair< pair<int, int>, pair<int, int> > rect[N];
vector< pair< pair< int, int >, pair< int, int > > > g;
pair<int, int> dp[2][N + 1];

int cf(int x, int y){
	if(y != 0 && (x == 0 || rect[x].X.Y < rect[y].X.Y)) return y;
	return x;
}

void inputs(){
	cin >> sx >> sy >> n;
	g.push_back(MP(MP(sx, N), MP(sy, sy)));
	for(int i = 1;i <= n;i++){
		cin >> rect[i].X.X >> rect[i].Y.X >> rect[i].X.Y >> rect[i].Y.Y;
		if(rect[i].X.X > rect[i].X.Y) swap(rect[i].X.X, rect[i].X.Y);
		if(rect[i].Y.X > rect[i].Y.Y) swap(rect[i].Y.X, rect[i].Y.Y);
		//sqX.push_back(rect[i].X.X), sqX.push_back(rect[i].X.Y);
		g.push_back(MP(MP(rect[i].X.X, i), rect[i].Y));
		g.push_back(MP(MP(rect[i].X.Y + 1, -i), rect[i].Y));
	} 
}

int getDist(pair<int, int> x, pair<int, int> y){
	return abs(x.X - y.X) + abs(x.Y - y.Y);
}

void sweep(){
	sort(g.begin(), g.end());
	for(auto tmp: g){
		if(tmp.X.Y > 0){
			int z = (tmp.X.Y) != N;
		//	cerr << "1";
			nxt[0][tmp.X.Y] = root.get(-INF, INF, tmp.Y.X - z);
		//	cerr << "2";
			nxt[1][tmp.X.Y] = root.get(-INF, INF, tmp.Y.Y + z);
		//	cerr << "3";
			if(z) root.upd(-INF, INF, tmp.Y.X, tmp.Y.Y, tmp.X.Y);			
		//	cerr << "4\n";
		}	
	}
	for(auto tmp: g){
		int id = tmp.X.Y;
		if(id > 0 && id != N) continue;
		if(id < 0) id = -id;
		int z = (id != N);
  		if(!nxt[0][id]) 
  			dp[0][id] = MP(0, 0), ans[0][id] = getDist(MP(0, 0), MP(tmp.X.X, tmp.Y.X - z));
  		else {
  			int v0 = ans[0][nxt[0][id]] + getDist(MP(rect[nxt[0][id]].X.Y + 1, rect[nxt[0][id]].Y.X - 1), MP(tmp.X.X, tmp.Y.X - z));
  			int v1 = ans[1][nxt[0][id]] + getDist(MP(rect[nxt[0][id]].X.Y + 1, rect[nxt[0][id]].Y.Y + 1), MP(tmp.X.X, tmp.Y.X - z));
  			if(v0 < v1) dp[0][id] = MP(0, nxt[0][id]), ans[0][id] = v0;
  			else dp[0][id] = MP(1, nxt[0][id]), ans[0][id] = v1;
  		}
  		if(!nxt[1][id]) 
  			dp[1][id] = MP(0, 0), ans[1][id] = getDist(MP(0, 0), MP(tmp.X.X, tmp.Y.Y + z));
  		else {
  			int v0 = ans[0][nxt[1][id]] + getDist(MP(rect[nxt[1][id]].X.Y + 1, rect[nxt[1][id]].Y.X - 1), MP(tmp.X.X, tmp.Y.Y + z));
  			int v1 = ans[1][nxt[1][id]] + getDist(MP(rect[nxt[1][id]].X.Y + 1, rect[nxt[1][id]].Y.Y + 1), MP(tmp.X.X, tmp.Y.Y + z));
  			if(v0 < v1) dp[1][id] = MP(0, nxt[1][id]), ans[1][id] = v0;
  			else dp[1][id] = MP(1, nxt[1][id]), ans[1][id] = v1;
  		}
	}
	//cerr << ans[1][1] << "\n";
	cout << ans[0][N] << "\n";
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 
	inputs();
	sweep();
}                             

• Subtask 1: 0 / 100