APIO 왕국이 닌자들의 공격을 받고 있다. 닌자들은 공격할 때 그림자에 숨을 수 있고, 다른 사람들은 그들을 볼 수 없으며 매우 강하다. 왕이 살고 있는 APIO 성을 제외한 왕국의 다른 성들은 모두 함락 당하였다.

APIO 성의 정면에는 N개의 덤불들이 한 줄로 놓여있다. 이 덤불들은 1부터 M까지의 번호가 매겨져 있고, K명의 닌자들이 정확히 K개의 덤불에 숨어있다. APIO 성에는 M병의 경비병이 있다. 경비병 i는 덤불 Ai부터 덤불 Bi까지의 연속된 덤불들을 감시한다. 각 경비병은 자기가 경비하는 덤불들에 닌자가 있는지에 대해 보고한다. 여러분은 각 경비병들의 보고를 듣고, 어떤 덤불에 “닌자가 확실히 숨어있”는지를 왕에게 보고해야 한다. 숨어있는 어떠한 닌자들의 배치에 대해서, 한 덤불에 “닌자가 확실히 숨어있다”는 것은 경비병들의 보고와 모순이 되지 않아야 한다.

경비병들의 정보와 그들의 보고가 주어질 때, "닌자가 확실히 숨어있는" 모든 덤불을 찾아내는 프로그램을 작성하라.

[제약조건] 1 ≤ N ≤ 100,000 덤불의 수 1 ≤ K ≤ N 숨어있는 닌자들의 수 1 ≤ M ≤ 100,000 경비병들의 수

#1454 upload 23 done 5 how_to_reg 5

경비병 timer 1s memory 128MB

#1454

경비병 1s 128MB