Codeforces #225(383 Div1) B. Volcanoes

問題

nxnのグリッドがあり(1, 1)から(n, n)へ、上または右に移動することを繰り返して進む。
グリッドのうちm個には障害物があり、そのマスへは入れない。

(1, 1)から(n, n)へ進むことはできるか。

制約条件

n≦10^9
m≦10^5

方針

しんどい実装問。

上または右にしかいけないので、下から一行ずつ、行ける範囲を更新していけばよい。
ナイーブにやるとO(m^2)とかだけど、更新があるのは石があるところだけなので、
行ごとに石のある場所を持ってあげる、現在通行不能な範囲を平衡二分木で管理するとかやると全体でO(n + mlogm)になる。

ソースコード

いくらなんでももう少しマシな書き方があったはず。

const int MX = 100010;
int n, m, x[MX], y[MX];
bool dp[3 * MX];
vi v[3 * MX];

inline void fix(set<pi> &iv, const pi &p){
	int a = p.first, b = p.second;
	set<pi>::iterator it = iv.lower_bound(mp(a, b));
	if(it != iv.end() && ++it != iv.end() && it->first == b){
		int c = it->second;
		iv.erase(mp(a, b));
		iv.erase(mp(b, c));
		iv.insert(mp(a, c));
		fix(iv, mp(a, c));
		return;
	}
	it = iv.lower_bound(mp(a, b));
	if(it != iv.begin() && (--it)->second == a){
		int c = it->first;
		iv.erase(mp(a, b));
		iv.erase(mp(c, a));
		iv.insert(mp(c, b));
		fix(iv, mp(c, b));
	}
}
inline void ins(set<pi> &iv, int x){
	set<pi>::iterator it = iv.lower_bound(mp(x + 1, 0));
	if(it != iv.begin()){
		--it;
		if(it->first <= x && x < it->second) return;
	}
	iv.insert(mp(x, x + 1));
	fix(iv, mp(x, x + 1));
}
inline void del(set<pi> &iv, int x){
	set<pi>::iterator it = iv.lower_bound(mp(x + 1, 0));
	if(it == iv.begin()) return;
	--it;
	
	int a = it->first, b = it->second;
	if(x < a || x >= b) return;
	iv.erase(mp(a, b));
	if(a < x) iv.insert(mp(a, x));
	if(x + 1 < b) iv.insert(mp(x + 1, b));
}

int main(){
	scanf("%d%d", &n, &m);
	vi xs, ys;
	rep(i, m){
		scanf("%d%d", x + i, y + i);
		rep(j, 3){
			if(x[i] - 1 + j > 0 && x[i] - 1 + j <= n) xs.pb(x[i] - 1 + j);
			if(y[i] - 1 + j > 0 && y[i] - 1 + j <= n) ys.pb(y[i] - 1 + j);
		}
	}
	
	xs.pb(1); ys.pb(1); xs.pb(n); ys.pb(n);
	sort(all(xs)); xs.erase(unique(all(xs)), xs.end());
	sort(all(ys)); ys.erase(unique(all(ys)), ys.end());
	
	rep(i, m){
		int b = lower_bound(all(ys), y[i]) - ys.begin();
		v[b].pb(lower_bound(all(xs), x[i]) - xs.begin());
	}
	rep(i, ys.size()) sort(all(v[i]));
	
	int lim = v[0].size() ? v[0][0] : xs.size();
	rep(i, lim) dp[i] = 1;
	
	set<pi> iv;
	if(lim < xs.size()) iv.insert(mp(lim, xs.size()));
	
	rep(i, (int)ys.size() - 1){
		
		vi er;
		each(j, iv){
			
			int l = j->first;
			if(l == 0 || !dp[l - 1]) continue;
			
			l = upper_bound(all(v[i + 1]), l) - v[i + 1].begin() - 1;
			if(l >= 0 && (v[i + 1][l] == j->first || v[i + 1][l] == j->first - 1)) continue;
			
			int r = l + 1 < v[i + 1].size() ? v[i + 1][l + 1] : xs.size();
			r = min(r, j->second);
			
			for(int k = j->first; k < r; k++){
				dp[k] = 1;
				er.pb(k);
			}
		}
		rep(j, er.size()) del(iv, er[j]);
		rep(j, v[i + 1].size()) ins(iv, v[i + 1][j]), dp[v[i + 1][j]] = 0;
	}
	cout << (dp[xs.size() - 1] ? 2 * n - 2 : -1) << endl;
	
	return 0;
}