ABC 035C - オセロ

問題概要

C - オセロ
N個の文字列(初期値0i0i+1...0i+N)に対して、範囲を指定すると対象の要素が1⇔0と反転する。
範囲指定をQ回行った時、Nの文字列を答えよ。

解法

範囲指定の積み重ねの結果で表裏が決まるため、Imos法で解ける。

提出コード

n, q = map(int, input().split())
a = [0 for i in range(n + 2)]
for i in range(q):
    x, y = map(int, input().split())
    a[x] += 1
    a[y + 1] -= 1
for i in range(n + 1):
    if i == 0:
        continue
    a[i] = a[i - 1] + a[i]

s = ''
for i in range(1, n + 1):
    if a[i] % 2 == 0:
        s += '0'
    else:
        s += '1'
print(s)