Codeforces 131 E. Yet Another Task with Queens

問題

nxnのチェス盤にm個のクイーンが置かれている。
クイーンのうち、
他の0個のクイーンの効きにあるような駒の数、
他の1個のクイーンの効きにあるような駒の数、
……
他の8個のクイーンの効きにあるような駒の数
をそれぞれ求めよ。

制約条件

n≦10^5
m≦10^5

方針

効きごとにsetを作って駒を突っ込んで、
それぞれの駒に対して、両隣に駒があるかを見るという強引なことをやったら通った。

ソースコード

set<int> yoko[100000],tate[100000],dia1[200010],dia2[200010];
int n,m,ans[9];

void run()
{
	cin>>n>>m;
	vi ys,xs;
	rep(i,m){
		int y,x; cin>>y>>x;
		ys.pb(--y); xs.pb(--x);
		
		int d1=y-x+100000,d2=y+x;
		dia1[d1].insert(x); dia2[d2].insert(x);
		yoko[y].insert(x);
		tate[x].insert(y);
	}
	rep(i,m){
		int cnt=0;
		set<int>::iterator it;
		it=yoko[ys[i]].find(xs[i]);
		if(it!=yoko[ys[i]].begin())cnt++;
		if(++it!=yoko[ys[i]].end())cnt++;
		it=tate[xs[i]].find(ys[i]);
		if(it!=tate[xs[i]].begin())cnt++;
		if(++it!=tate[xs[i]].end())cnt++;
		
		int d1=ys[i]-xs[i]+100000, d2=ys[i]+xs[i];
		it=dia1[d1].find(xs[i]);
		if(it!=dia1[d1].begin())cnt++;
		if(++it!=dia1[d1].end())cnt++;
		it=dia2[d2].find(xs[i]);
		if(it!=dia2[d2].begin())cnt++;
		if(++it!=dia2[d2].end())cnt++;
		ans[cnt]++;
	}
	rep(i,9)cout<<ans[i]<<(i==8?"\n":" ");
}