Codeforces #225 Div1. B. Volcanoes

本番中方針は立ったけど、pretestまでしか通らなかった問題。
方針はあってたがバグがとりきれなかった。
結果は大量にWAが出ており、挑むべきでなかったかも。
http://codeforces.com/contest/383/problem/B

問題

NxNのグリッドがあり、左上(1,1)のセルから右下(N,N)のセルに移動したい。
このグリッド上で、M個のセルは火山があり、そのセルは移動できない。
移動は右または下にしかできない場合、(N,N)に到達できるか、またできる場合は最短距離を答えよ。

解法

右と下にしか移動できないので、(1,1)から(N,N)に移動するのは距離2(N-1)の手順しかない。
後は(N,N)に移動可能か判定する。
各X座標において、到達可能なY座標の範囲を(始点,終点)の配列の形でもち、処理していけばよい。

Nはかなり大きいが、火山セルのないX座標が複数続いても１つだけ処理すればよいのでNの大きさは関係ない。
実質O(M)で処理できるが、Mはそこまで大きくないので問題ない。

int N,M;
int X[100010],Y[100010];
map<int, set<int> > MM;

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M;
	ll ret=2*(N-1);
	int ma0=N,minn=1;
	
	
	FOR(i,M) {
		cin>>X[i]>>Y[i];
		if(X[i]==1) ma0=min(ma0,Y[i]-1);
		else MM[X[i]].insert(Y[i]);
	}
	
	int ng=0;
	vector<pair<int,int> > OK,OK2;
	
	OK.push_back(make_pair(1,ma0));
	ll prex=1;
	ITR(it,MM) {
		
		if(it->first!=prex+1) {
			j=OK.begin()->first;
			OK.clear();
			OK.push_back(make_pair(j,N));
		}
		
		OK2.clear();
		
		vector<pair<int,int> >::iterator oit=OK.begin();
		set<int>::iterator bit=it->second.begin();
		i=1;
		while(oit!=OK.end() && bit!=it->second.end()) {
			if(i>oit->first) oit->first=i;
			
			if(oit->first>oit->second) { oit++; continue; }
			if(*bit<oit->first) { bit++; continue;}
			if(*bit==oit->first) { bit++; oit->first++; continue;}
			OK2.push_back(make_pair(oit->first,*bit-1));
			i=*bit+1;
			bit++;
		}
		
		if(bit==it->second.end()) {
			while(oit!=OK.end()) {
				if(i>oit->first) oit->first=i;
				if(oit->first<=oit->second) break;
				oit++;
			}
			if(oit!=OK.end() && oit->first<=N) OK2.push_back(make_pair(oit->first,N));
		}
		
		swap(OK,OK2);
		if(OK.empty()) {
			cout << -1 << endl;
			return;
		}
		prex=it->first;
	}
	
	
	if(prex!=N) {
		j=OK.begin()->first;
		OK.clear();
		OK.push_back(make_pair(j,N));
	}
	
	if(OK.back().second<N) cout << -1 << endl;
	else cout << ret << endl;
}

まとめ

えらく実装が面倒だった。Editorialを見ると想定解っぽいけど…。