← 返回题目列表

AtCoder · abc035_c

C. 奥赛罗

中文机器翻译题面 查看原题

問題文

在黑色方面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
  • 这种情况满足部分点相加约束。 您将获得一系列