TopCoder SRM 595, Division 1, Level 1 : LittleElephantAndIntervalsDiv1

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12822&rd=15707

概要

M 個のボールが一列に並んでいる。
これらのボールの色を白または黒に何度か塗り替えることができる。
i 回目の操作では [ L[ i ], R[ i ] ] の範囲のボールの色を塗り替える。
一連の操作の終了後に作ることができる塗られ方の総数を求めよ。

解法

二つのボールについて、最後の色が塗られた時刻が異なるもの同士は独立に塗ることができます。
一度の操作では二色の内いずれかに塗ることができるので、塗らる時刻の種類を N とすると 通りの塗られ方が存在します。
各ボールが最後に塗られる時刻の求め方ですが、列の幅が高々 1,000 なので毎回愚直に [ L[ i ], R[ i ] ] の範囲を塗りつぶしても間に合います。
最後に 2 の冪乗を求めれば答えになります。

コード

typedef long long LL;
typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

class LittleElephantAndIntervalsDiv1
{
public:
	long long getNumber( int M, vector <int> L, vector <int> R )
	{
		const int N = L.size();

		VI last( M, -1 );

		REP( i, 0, N )
		{
			REP( j, L[i] - 1, R[i] )
			{
				last[j] = i;
			}
		}

		LL num = set<int>( ALL( last ) ).size() - ( find( ALL( last ), -1 ) != last.end() ? 1 : 0 );
		return 1LL << num;
	}
};