2014-2015 ACM-ICPC, NEERC, Moscow Subregional Contest B. Bring Your Own Bombs

問題

無限に広いグリッドがある。
N個の長方形があり、(xi, yi)を左下, (Xi, Yi)を右上としていて、範囲のマスにそれぞれ一人ずつ人間がいる。
長方形は重ならない。
M個の爆弾があり、(bxi, byi)に置かれていて、p1iの確率で、y = byiの直線にいる人が全員死に、
p2iの確率でx = bxiの直線にいる人が全員死ぬ。両方が同時に起こることはなく、1 - p1i - p2iの確率でその爆弾は全く無害になる。誘爆したりもしない。

爆弾で死ぬ人の数の期待値を求めよ。

http://codeforces.com/gym/100519/problem/B

制約条件

N≦10^5
M≦10^5

メモ

リクルート主催のCode Festivalの8位入賞の賞品として上海ツアー（プロコン＋観光）を獲得したのでそれに向けてatetubou君と練習会をした。（何故かチーム形式で練習した）

毎回毎回忘れる方針の平面走査。
自分がノーアイディアだったところにatetubou君が解法を教えてくれたけど他の問題でハマって時間が足りずに実装しきれず。
とは言うものの、解きなおしたら12WAも出したので1時間あっても結構きつかったかもしれない。

方針

生き残る人数の期待値を数えるようにすると処理しやすい。
x座標方向に座標圧縮する。
y座標方向に走査する。

x座標ごとに、そのx座標に爆弾が来ない確率を求めておく。
これを累積和にしておけば、横方向の爆弾がない範囲では、
爆弾が来ない期待値は、(累積和) * 高さのような感じで求められる。

横方向の爆弾があると期待値が変わるので、平面走査して処理する。

人のいる区間開始がきたら、今処理中の区間を増やす。
人のいる区間終了がきたら、その区間の高さ x 幅だけ答えに足す。
爆弾がきたら、今処理中の区間を一瞬退避して、そのy座標のときだけは、更に生き残る確率がp_horizontal[y]減るようにして答えに足す。

人が入っている領域の中に爆弾があるときは確率が独立でないため、更にそこだけ別処理が必要で、(このx座標での生き残り確率) / (1 - この爆弾の縦の爆発確率) * (1 - 縦確率 - 横確率)として答えに加算する。

舌たらずな感じなのでソースコードを参照。

ソースコード

typedef long double D;
#define F first
#define S second

const int MX = 400010;
int n, m;
D psum[MX];

int main(){
	scanf("%d%d", &n, &m);
	vi xs;
	vi rx(n), ry(n), RX(n), RY(n);
	vi bx(m), by(m);
	vector<D> pyoko, ptate;
	D area = 0;
	
	//区間はじまり / おわり (y, +-1, id)
	//爆弾(y, 0, id)
	vector<pair<pi, int> > event;
	
	rep(i, n){
		scanf("%d%d%d%d", &rx[i], &ry[i], &RX[i], &RY[i]); RX[i]++;
		xs.pb(rx[i]);
		xs.pb(RX[i]);
		
		event.pb(mp(mp(ry[i],-1), i));
		event.pb(mp(mp(RY[i], 1), i));
		area += (RX[i] - rx[i]) * (RY[i] - ry[i] + 1.0);
	}
	rep(i, m){
		int a, b; scanf("%d%d%d%d", &bx[i], &by[i], &a, &b);
		xs.pb(bx[i]); xs.pb(bx[i] + 1);
		pyoko.pb(a / 100.0);
		ptate.pb(b / 100.0);
		
		event.pb(mp(mp(by[i], 0), i));
	}
	sort(all(xs));
	xs.erase(unique(all(xs)), xs.end());
	
	rep(i, xs.size() - 1) psum[i + 1] = xs[i + 1] - xs[i];
	rep(i, m){
		int k = lower_bound(all(xs), bx[i]) - xs.begin();
		psum[k + 1] *= 1.0 - ptate[i];
	}
	rep(i, xs.size()) psum[i + 1] += psum[i];
	
	sort(all(event));
	D ans = -area; //alive 
	D cursum = 0;
	set<pi> curiv;
	
	rep(it, event.size()){
		int type = event[it].F.S;
		if(type == 0){
			
			vector<pi> bomb; //(xpos, id);
			D prod = 1.0;
			D tmpsum = cursum;
			
			for(int i = it; i < event.size() && event[it].F.F == event[i].F.F && event[i].F.S == 0; i++){
				int id = event[i].S;
				bomb.pb(mp(bx[id], id));
				prod *= 1.0 - pyoko[id];
			}
			sort(all(bomb));
			
			
			rep(i, bomb.size()){
				set<pi>::iterator it = curiv.lower_bound(pi(bomb[i].F + 1, -inf));
				if(it == curiv.begin()) continue;
				--it;
				
				if(it->first <= bomb[i].F && bomb[i].F < it->second){
					int id = bomb[i].S;
					int x = lower_bound(all(xs), bomb[i].F) - xs.begin();
					int l = lower_bound(all(xs), it->F) - xs.begin();
					int r = lower_bound(all(xs), it->S) - xs.begin();
					tmpsum -= psum[r] - psum[l];
					
					ans += (psum[x + 1] - psum[x]) / (1.0 - ptate[id]) * (1.0 - ptate[id] - pyoko[id]);
				}
			}
			ans += tmpsum * prod;
			ans -= cursum;
			
			it += (int)bomb.size() - 1;
			
			//dbg(tmpsum);
		}
		else if(type == -1){
			
			int id = event[it].S;
			int l = lower_bound(all(xs), rx[id]) - xs.begin();
			int r = lower_bound(all(xs), RX[id]) - xs.begin();
			cursum += psum[r] - psum[l];
			curiv.insert(mp(rx[id], RX[id]));
			
			//dbg(cursum);
		}
		else{
			int id = event[it].S;
			int l = lower_bound(all(xs), rx[id]) - xs.begin();
			int r = lower_bound(all(xs), RX[id]) - xs.begin();
			
			cursum -= psum[r] - psum[l];
			ans += (psum[r] - psum[l]) * (RY[id] - ry[id] + 1);
			curiv.erase(mp(rx[id], RX[id]));
		}
	}
	#if 0
	rep(i, xs.size()) cerr<<psum[i+1]-psum[i]<<(i==xs.size()-1?"\n":" ");
	dbg(ans);
	#endif
	printf("%.20f\n", (double)(-ans));
	return 0;
}