Informatica Online Judge

  눈 내리는 겨울 밤 (L) [1396 / 0574]

Time Limit(Test case) : 1500 (ms)
Number of users who solved : 74   Total Tried : 432


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

[JKJeong 2015]

Background

경곽이는 라인월드에 살고 있다.

라인월드는 수직선으로 이루어진 나라이다. 라인월드에도 겨울이 왔다.

라인월드에는 눈이 내리면 그 영역에 그대로 쌓인다.

만약 구간 a로부터 b까지 (양 끝 포함) w만큼의 눈이 내린다면 [a, b]구간에는 모두 눈이 w만큼의 높이로 쌓인다.

이번 라인월드는 기후가 바뀌어 이전 라인월드보다 훨씬 더 많은 눈이 자주 내린다. ㅠㅠ

예를 들어 라인월드의 땅의 길이가 10이고, 다음과 같이 3번의 눈이 왔다고 가정하자.

1) 1 5 2
2) 2 4 3
3) 3 10 1

처음에 1부터 5영역에 2만큼 눈이 내리므로 라인월드에 쌓인 눈은 다음과 같다.

2 2 2 2 2 0 0 0 0 0

다음에 2부터 4까지 3의 눈이 내리므로 다음과 같이 된다.

2 5 5 5 2 0 0 0 0 0

마지막으로 3부터 10까지 1이 내리므로

2 5 6 6 3 1 1 1 1 1

이 되어 최종적으로 눈이 쌓인 모습이 된다.

라인 월드에 눈이 내린 정보가 주어질 때,마지막에 쌓인 모양을 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 라인월드의 크기 n과 눈이 내리는 횟수 q가 공백으로 구분되어 입력된다.

둘 째줄부터 q줄에 걸쳐서 눈이 내리는 구간의 시작과 끝을 나타내는 정수 a, b와 눈의 양을 나타내는 수 w가 공백으로 구분되어 입력된다.

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

[Sub-Task Info]
#1 : n <= 10, q <= 10,000 (33%)
#2 : n <= 2000, q <= 10,000 (33%)
#3 : 추가제한 없음

Output

라인월드 1부터 n까지 쌓인 눈을 공백으로 구분하여 출력한다.

IO Example

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

출력
2 5 6 6 3 1 1 1 1 1

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