WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #182 Div2 A "Eugeny and Array"

問題

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

ユージャニー(?)はn個の整数 a_1, a_2, ... a_n という配列aを持っている。
この配列の各要素は -1 か 1 である。
また、m個のクエリがある。

i番目のクエリでは li ri( 1 <= li <= ri <= n ) という整数のペアが与えられる。
応答は、もし配列の要素を好きなように再配置して
a_li + a_li+1 + ... + a_ri = 0とする事が可能であれば、1を出力せよ。
そうでなければ0を出力せよ。

制約

1 <= n, m <= 2 * 10^5


考えた事

liからriの範囲をlenとすると、
lenが偶数でないとダメ
配列全体に1と-1がそれぞれlen / 2個以上ないとダメ


ソースコード

int main() {
    int N, M;
    cin >> N >> M;

    int plus = 0, minus = 0;
    for( int i = 0; i < N; i++ ){
        int t;
        cin >> t;
        if( t == 1 ) plus++;
        if( t == -1 ) minus++;
    }

    for( int i = 0; i < M; i++ ){
        int l, r;
        cin >> l >> r;
        int n = r - l + 1;
        bool ok = (n % 2 == 0) && (n / 2 <= plus) && (n / 2 <= minus);
        printf( "%d\n", ok ? 1 : 0 );
    }
}