TopCoder SRM 595 Div1 Easy LittleElephantAndIntervalsDiv1

SRM595は午前中回なので不参加。
本番出てたらEasyはあっさり解けたけどMediumは時間内に計算量を落としきれずアウトで、レート微増だったかな。
http://community.topcoder.com/stat?c=problem_statement&pm=12822

問題

1～Mまでのボールが１列に並んでいる。
これらのボールに色を塗る機会がN回あり、i回目の機会ではL[i]番～R[i]番までの全てのボールを白か黒のどちらか片方に塗ることができる。
N回色を塗った後にありうるボールの色の組み合わせ数を答えよ。

解法

同じボールが複数回塗られることもある。
そこで、各ボールが最終的に何回目に塗った色が残るかをカウントする。
そして最後まで残る塗布の回数を求め、２の累乗をとればよい。

計算量はO(MN)なので余裕。
Mを極端に大きくして座標圧縮とかしてもよさそうな問題。

class LittleElephantAndIntervalsDiv1 {
	int N;
	int mat[1002],vis[50];
	public:
	long long getNumber(int M, vector <int> L, vector <int> R) {
		int i,x,y;
		N=L.size();
		ZERO(mat);
		FOR(i,N) for(x=L[i];x<=R[i];x++) mat[x]=i+1;
		ZERO(vis);
		FOR(i,M) vis[mat[i+1]]++;
		ll ret=1;
		FOR(i,N) if(vis[i+1]) ret<<=1;
		return ret;
	}
};

まとめ

Div1 Easyにしては簡単な問題。