A skyline de Nova Iorque é constituida por vários prédios de diferentes alturas. No contexto deste problema vamos assumir que cada prédio é um retângulo com um lado no eixo dos X com coordenadas contidas num retângulo de altura N e comprimento M. Cada prédio tem um índice associado, um inteiro entre 1 e S. Um prédio é descrito por por três valores (todos inteiros positivos): a menor coordenada no eixo dos X; a maior coordenada no eixo dos X; a altura do prédio.
Uma fotografia da cidade é uma grelha de N linhas por M colunas que representa os prédios de Nova Iorque. Cada célula da grelha contém um inteiro entre 0 e S, onde 0 representa um espaço vazio (ausência de um prédio) e um valor positivo representa o índice de um prédio.
Os prédios têm uma certa ordem, que representa a terceira dimensão espacial. Assim, o primeiro prédio é o que está à frente e o último é o que está mais atrás. Um prédio obstrui um outro se os seus retângulos se intersetarem, neste caso o segundo dos dois na ordem dos prédios será parcialmente ou totalmente invisível na fotografia.
Vejamos um exemplo do anterior para clarificação. Seja N = 4 e M = 5 e vamos supor que temos 3 prédios, na seguinte ordem: o prédio verde (2, 3, 2) de índice 2, isto é, isto é o retângulo com menor coordenada X de 2, maior coordenada X de 3 e de altura 2; o prédio vermelho (1, 2, 3) de índice 1; o prédio azul (3, 4, 3) de índice 5. A imagem à esquerda mostra uma representação espacial deste exemplo e a imagem da direita mostra a fotografia correspondente.
A grelha que representa a fotografia anterior é:
0 0 0 0 0 1 1 5 5 0 1 2 2 5 0 1 2 2 5 0
Nesta primeira parte é nos dada uma fotografia da cidade. Esta fotografia será sempre válida, ou seja, representa necessariamente um conjunto válido de retângulos. O objetivo é contar quantos prédios distintos são visíveis na fotografia. Nota que os índices dos prédios não têm de ser consecutivos.
Se N = 4, M = 5 e S = 10 e tivermos a seguinte fotografia (igual ao exemplo da introdução):
0 0 0 0 0 1 1 5 5 0 1 2 2 5 0 1 2 2 5 0
São visíveis 3 prédios distintos, o de índice 1, o de índice 2 e o de índice 5.
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
| 1 ≤ M, N ≤ 300 | Dimensões da cidade | |
| 1 ≤ S ≤ 106 | Índice máximo de um prédio |
Os casos de teste desta parte do problema estão organizados num grupo com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 10 |
Na segunda parte do problema é nos dado um conjunto de Q prédios pela sua ordem. Os índices destes prédios estão por ordem crescente, ou seja, o primeiro prédio tem índice 1, o segundo tem índice 2, etc. O objetivo é determinar a fotografia que estes prédios geram.
Se N = 4, M = 4 e Q = 2 e tivermos os retângulos (1, 2, 3), isto é o retângulo com menor coordenada X de 1, maior coordenada X de 2 e de altura 3, e o retângulo (2, 3, 2), por esta ordem, então a fotografia que estes geram é:
0 0 0 0 1 1 0 0 1 1 2 0 1 1 2 0
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
| 1 ≤ M, N ≤ 300 | Dimensões da cidade | |
| 1 ≤ Q ≤ 5 · 104 | Número de prédios |
Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 2 | 10 | 1 ≤ Q ≤ 100 |
| 3 | 30 |
Na última parte do problema é nos dada uma fotografia da cidade. Esta fotografia pode não ser válida, ou seja, pode não existir nenhum conjunto de prédios que a gere. O objetivo é determinar se existe um conjunto de retângulos e índices correspondentes que gere a fotografia dada e se sim, indicar pelo menos um tal conjunto (podem existir vários, basta indicar um).
Se N = 4, M = 4 e S = 3 e tivermos a seguinte fotografia:
0 0 0 0 1 1 3 3 1 2 2 3 1 2 2 3
Esta fotografia é gerada pelos seguintes 3 prédios (dados na ordem correta):
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
| 1 ≤ M, N ≤ 300 | Dimensões da cidade | |
| 1 ≤ S ≤ 300 | Índice máximo de um prédio |
Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 4 | 30 | 1 ≤ M, N, S ≤ 30 |
| 5 | 20 |
Os casos de teste do problema estão organizados em 5 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Parte | Restrições adicionais |
|---|---|---|---|
| 1 | 10 | Parte I | |
| 2 | 10 | Parte II | 1 ≤ Q ≤ 100 |
| 3 | 30 | Parte II | |
| 4 | 30 | Parte III | 1 ≤ M, N, S ≤ 30 |
| 5 | 20 | Parte III |
Nota: O formato de input difere para a parte II
A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 refere-se à Parte II, se for 3 então refere-se à Parte III.
Nas partes I e III, segue-se uma linha com três inteiros separados por espaços, primeiro N, representando a altura da cidade seguido de M, o comprimento da cidade, finalmente S, o índice máximo de um prédio.
Seguem-se N linhas, cada uma contendo M inteiros entre 0 e S separados por espaços, representando uma fotografia.
Na parte II, segue-se uma linha com três inteiros separados por espaços, primeiro N, representando a altura da cidade seguido de M, o comprimento da cidade, finalmente Q, o número de prédios.
Seguem-se Q linhas, cada uma contendo 3 inteiros separados por espaços, respetivamente: a menor coordenada no eixo dos X, a maior coordenada no eixo dos X, a altura do prédio.
O output deve ser apenas um inteiro, o número total de prédios visíveis.
O output deve ser conter N linhas, cada uma com M inteiros separados por espaços, representando a fotografia.
O output deve começar com um inteiro Q, o número total de prédios no conjunto gerado ou o valor -1, caso não exista nenhum conjunto válido.
Devem seguir-se Q linhas representando os prédios na ordem correta, cada uma contendo 4 inteiros separados por espaços, respetivamente: a menor coordenada no eixo dos X, a maior coordenada no eixo dos X, a altura do prédio, o índice do prédio.
Nota que podem haver várias respostas corretas, só é necessário imprimir uma.
1 4 5 10 0 0 0 0 0 1 1 5 5 0 1 2 2 5 0 1 2 2 5 0
3
Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.
2 4 4 2 1 2 3 2 3 2
0 0 0 0 1 1 0 0 1 1 2 0 1 1 2 0
Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.
3 4 4 3 0 0 0 0 1 1 3 3 1 2 2 3 1 2 2 3
3 2 3 2 2 3 4 3 3 1 2 3 1
Este exemplo corresponde ao exemplo da Parte III mencionado no enunciado.