Informatica Online Judge

  벽 칠하기 [0877 / 036D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 224   Total Tried : 2176


The Champion of this Problem (C++) : gs18080 - ms / 484byte
My Best Submission (C++) : N/A

[JeongHJ 2013]

Background

경곽이는 seaguy선생님으로부터 정보실 벽에 페인트를 칠하라는 부탁을 받았다. 벽은 다음 그림과 같이 n개의 조각으로 구성되어 있다.

경곽이는 조금 변덕이 심해서 벽의 일부 연속된 구간에 원하는 색을 칠하고 감상을 하다가 마음에 들지 않으면 다시 벽의 일정 구간을 원하는 색으로 칠하기를 반복하였다. 마침내 경곽이가 벽의 색이 마음에 들어 색칠하기를 종료한다.

최종적으로 벽의 상태를 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 벽의 조각 수 n과 벽에 색칠하기의 반복 횟수 m이 입력된다.
두 번째 줄에 1부터 m까지의 벽의 폐구간 [a, b]와 페인트의 색 번호 c가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n, m, c <= 100 000
1 <= a <= b <= n

Output

벽에 최종적으로 칠해진 페인트 색의 번호를 공백으로 구분하여 출력한다. 단, 벽에 색이 칠해지지 않은 칸의 경우는 0으로 출력한다.

IO Example

입력1
5 3
1 3 1
2 3 2
4 4 1

출력
1 2 2 1 0

* 페인트를 칠하는 과정은 1 1 1 0 0 → 1 2 2 0 0 → 1 2 2 1 0 로 변경되며 최종적으로 벽의 색은 1 2 2 1 0의 상태가 된다.

입력2
8 7
1 3 1
2 6 2
4 7 3
6 8 4
2 8 5
1 6 6
1 2 7

출력
7 7 6 6 6 6 5 5

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]