Codeforces #182, Division 2, A : Eugeny and Array

問題文

http://codeforces.com/contest/302/problem/A

概要

1 と -1 からなる列 a が与えられる。
以下の様なクエリ　l, r を m 個処理せよ

• a を並び替えて区間 [ l, r ] の和を 0 できれば 1 、そうでないなら 0 を答える

解法

a を好きに並び替えることができるので、全体に 1 と -1 がいくつずつあるかだけ考えればよいことになります。
区間 [ l, r ] が決まったとき、区間に含まれる要素の数は r - l + 1 です。
これが奇数の場合、0 を作ることはできません。
偶数の場合、1 の数と -1 の数がどちらもこの半分以上あれば 0 を作れます。

コード

typedef vector<int> VI;

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


int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, m;
	cin >> n >> m;
	
	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	int posi = count( ALL( as ), 1 );
	int nega = count( ALL( as ), -1 );

	REP( i, 0, m )
	{
		int l, r;
		cin >> l >> r;

		int total = ( r - l + 1 );
		int num = total / 2;

		if ( total % 2 || min( posi, nega ) < num )
		{
			cout << 0 << endl;
		}
		else
		{
			cout << 1 << endl;
		}
	}

	return 0;
}