AtCoder ABC #186 (パナソニックプログラミングコンテスト) : F - Rook on Grid

見落としがあってだいぶ手直しが入ってタイムロス。
https://atcoder.jp/contests/abc186/tasks/abc186_f

問題

H*Wのグリッドがあり、いくつかのマスに障害物がある。
左上マスから、飛車の移動2手で移動可能なマスは何マスあるか。

解法

各列で上から到達可能なマスかどうかを0/1で管理し、区間の和をBITで高速に求められるようにしておく。
まず1行目は、障害物がなければ全列、あれば最も左の障害物の手前まで移動可能なので、そのように0/1とBITを初期化しておく。

以下2行目以降を見ていく。
障害物があれば、まず0/1とBITを更新しよう。

• 1列目が到達可能な場合
  • その行において一番左の障害物までは任意に移動可能。それより右は上からしか侵入できないので、BITでそのようなマスを数え上げる。
• 1列目が到達不可能な場合
  • 行は上からしか侵入できないので、BITでそのようなマスを数え上げる。

int H,W,N;
int Y[202020],X[202020];
vector<int> R[202020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,20> bt;
int did[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>N;
	FOR(i,N) {
		cin>>Y[i]>>X[i];
		Y[i]--,
		X[i]--;
		R[Y[i]].push_back(X[i]);
	}
	FOR(i,200001) R[i].push_back(W), sort(ALL(R[i]));
	ll ok=R[0][0];
	FOR(x,R[0][0]) bt.add(x,1), did[x]=1;
	
	int a=1;
	for(y=1;y<H;y++) {
		if(R[y][0]==0) a=0;
		FORR(x,R[y]) if(did[x]==1) {
			did[x]=0;
			bt.add(x,-1);
		}
		if(a==1) {
			ok+=R[y][0]+bt(W)-bt(R[y][0]);
		}
		else {
			ok+=bt(W);
		}
	}
	
	cout<<ok<<endl;
}

まとめ

最初1行目・1列目を特別扱いすることを忘れており、その手戻りでタイムロスしてしまった。