C - オセロ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

黒の面に0、白の面に1が書かれた N 個のオセロの駒が、どの駒も黒の面が上を向くように一列に並べられています。その後、ある区間にある駒を全て裏返すという操作が Q 回だけ行なわれました。 具体的には i 回目の操作においては、左から l_i 番目の駒から r_i 番目の駒までの駒全てが裏返されました。

最終的な盤面を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

N Q
l_1 r_1
.
.
.
l_Q r_Q
  • 1 行目に駒の数と操作回数を表す 2 つの整数 N,Q (1≦N,Q≦200,000) が空白区切りで与えられる。
  • 2 行目から続く Q 行のうち i 行目においては、 i 回目の操作の範囲を表す 2 つの整数 l_i, r_i (1≦l_i≦r_i≦N) が空白区切りで与えられる。

出力

最終的な盤面を表す文字列 S を 1 行に出力せよ。 S の左から i 文字目は左から i 番目の駒の上向きの面に書かれた数字となる。改行を忘れないこと。

部分点

この問題には部分点が設定されている。

  • 1≦N,Q≦2,000 を満たすデータセットに正解した場合、 60 点が与えられる。
  • 追加制約のないデータセットに正解した場合は、追加で 40 点が与えられ、合計 100 点が得られる。

入力例 1

5 4
1 4
2 5
3 3
1 5

出力例 1

01010
  • 盤面ははじめ00000です。
  • 1 回目の操作により、 盤面は11110となります。
  • 2 回目の操作により、 盤面は10001となります。
  • 3 回目の操作により、 盤面は10101となります。
  • 4 回目の操作により、 盤面は01010となります。
  • 最終的な盤面である01010が求める答えです。
  • このケースは部分点の追加制約を満たします。

入力例 2

20 8
1 8
4 13
8 8
3 18
5 20
19 20
2 7
4 9

出力例 2

10110000011110000000
  • このケースは部分点の追加制約を満たします。