| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 273 | 95 | 82 | 45.055% |
시간 너머 저 멀리에서 전해진 기록법과 해독법을 통해, 흩어진 기록은 새로운 형태를 갖추기 시작했다.
조각난 흔적들은 완전하지 않았지만, 브루는 그 흐름 속에서 과거의 장면들을 조심스레 해석해 나갔다.
오래전, 섬의 중심에서 태어난 빛이 땅 위로 흘러내리기 시작했다. 그것은 단순한 광원이 아니었다. 질서와 균형을 품은 빛, 세상의 이치를 비추는 힘이었다.
고대의 사람들은 이 새로운 힘이 균형을 이루도록 하기 위해 곳곳에서 흐르는 빛의 색을 조정하려 했다. 그들은 빛을 조정하면 세상에 조화가 깃들 것이라 믿었다.
빛이 처음으로 흐르던 그날의 기억을 지켜보고, 빛과 그림자가 나뉜 이유를 찾아보아라.
빛이 흐르는 공간은 $N$행 $M$열 크기의 격자로 표현된다. 빛은 제1ドル$행으로부터 시작해, 아래로 곧게 흘러 제$N$행에 이른다. 이때 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 칸을 $(r,c)$로 표기한다.
각 열에 흐르는 빛은 고유의 색을 가지며, 그 색은 1ドル$부터 $T$까지의 번호를 가진 $T$가지 색 중 하나이다. $i$번 열로 흐르는 빛은 색 $A_i$로 시작하여, 특별한 변화가 없다면 아래로 곧게 이어지며 지나간 모든 칸을 해당 색으로 채운다.
사람들은 빛의 균형을 맞추기 위해 격자 중간에 빛의 색을 바꾸는 $K$개의 구조물을 배치했다. 이 구조물들은 인접한 두 행 사이 연속한 열 위에 놓이며, 그 아래로 흐르는 빛의 색을 특정한 색으로 바꾸는 역할을 한다. 두 구조물은 겹치지 않지만, 그 끝은 맞닿을 수 있다.
$T$가지 색 각각에 대해, 해당 색으로 채워진 칸의 수를 알아내어라.
첫 줄에는 공간의 크기를 나타내는 두 정수 $N,ドル $M,ドル 색의 가짓수 $T,ドル 구조물의 수 $K$가 공백으로 구분되어 주어진다.
둘째 줄에는 각 열의 초기 빛의 색을 나타내는 정수 $a_1,a_2,\cdots ,a_M$이 공백으로 구분되어 주어진다.
이후 $K$개의 줄에 걸쳐, 각 구조물의 정보를 나타내는 네 정수 $r_i,s_i,e_i,c_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 구조물이 $r_i-1$행과 $r_i$행 사이의 격자선 $s_i$열부터 $e_i$열까지를 덮는 구역에 설치되었고, 해당 구조물이 빛의 색을 $c_i$로 바꾼다는 의미이다.
1ドル$번부터 $T$번까지의 색에 대해, 각 색으로 채워진 칸의 수를 순서대로 한 줄에 출력하여라.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $K = 0$ |
| 2 | 8 | $K = 1$ |
| 3 | 19 | $N \le 100, M \le 100, K \le 100$ |
| 4 | 25 | $N \le 2000, M \le 2000, K \le 2000$ |
| 5 | 6 | $N \le 3000, M \le 3000$ |
| 6 | 39 | 추가 제한 조건이 없다. |
9 5 4 5 1 2 3 2 4 3 1 3 3 6 4 5 2 6 2 3 4 4 3 4 1 8 3 3 1
8 13 13 11
7 6 3 1 1 2 3 2 3 2 5 3 5 1
16 18 8
Contest > BOJ User Contest > BCF > BCF 2025 I번