문제 1025 케이크
[만든사람 : ]
문제 설명
세종이는 소문난 케이크 매니아이다. 세계 각국의 케이크를 먹어보던 세종이는, 이젠 직접 자신만의 케이크를 만들기로 했다.
세종이는 길이가 N인 판에 서로 다른 맛의 스펀지케이크 M개를 쌓으려고 한다. 각 i번 케이크를 해당 판의 구간 [ai, bi]에 di만큼의 두께로 층층이 쌓는다.
스펀지케이크는 가볍고 무르기 때문에 아래에 받쳐주는 판이 없으면 다른 무언가가 받쳐질 때까지 무너져내린다.
세종이는 길이가 N인 판에 서로 다른 맛의 스펀지케이크 M개를 쌓으려고 한다. 각 i번 케이크를 해당 판의 구간 [ai, bi]에 di만큼의 두께로 층층이 쌓는다.
스펀지케이크는 가볍고 무르기 때문에 아래에 받쳐주는 판이 없으면 다른 무언가가 받쳐질 때까지 무너져내린다.
위쪽에 쌓인 케이크를 받쳐주는 판이나 케이크가 없어 아래로 무너져내린다.
세종이는 M개의 케이크를 다 쌓고 만들어진 최종 두께를 알고 싶다. 길이 N 판에 놓인 케이크의 최종 두께를 알려주자.
입력 설명
첫 줄에 판의 길이 N과 케이크의 수 M이 공백을 사이에 두고 주어진다. (1 <= N, M <= 100,000)
이후 M개의 줄에 각 케이크를 놓는 구간과 두께 ai, bi, di (1 <= ai <= bi <= N, 1 <= di <= 10,000)가 공백을 사이에 두고 주어진다.
이후 M개의 줄에 각 케이크를 놓는 구간과 두께 ai, bi, di (1 <= ai <= bi <= N, 1 <= di <= 10,000)가 공백을 사이에 두고 주어진다.
출력 설명
세종이의 케이크 판에 단위길이마다 쌓인 케이크의 두께를 출력한다.
입력 예시 복사
7 3
2 5 1
1 4 2
3 7 3
출력 예시 복사
2 3 6 6 4 3 3
출처/분류