문제
대통령 K는 N×N 격자에 패턴을 디자인하려고 합니다. 각 셀은 정수로 표현되는 색상으로 칠해집니다. i번째 행(1 ≤ i ≤ N)과 j번째 열(1 ≤ j ≤ N)의 셀을 (i, j)로 표기합니다.
현재, 첫 번째 행과 첫 번째 열의 셀들은 이미 칠해져 있습니다. 구체적으로, 모든 1 ≤ i ≤ N에 대해 셀 (i, 1)은 색상 Aᵢ로, 모든 1 ≤ j ≤ N에 대해 셀 (1, j)은 색상 Bⱼ로 칠해져 있으며, A₁ = B₁입니다.
나머지 미칠해진 셀들은 다음 절차에 따라 차례대로 칠합니다.
• i = 2, 3, …, N에 대해, i번째 행의 셀들을 다음과 같이 칠합니다:
◦ j = 2, 3, …, N에 대해, 셀 (i, j)는 아래 두 값 중 더 큰 값으로 칠합니다.
셀 (i − 1, j)의 색상
* 셀 (i, j − 1)의 색상
(만약 두 색상이 동일하면 그 색상으로 칠합니다.)
최종적으로 모든 N²개의 셀이 칠해진 후, 대통령 K는 가장 많이 칠해진 색상이 무엇이며, 그 색상이 몇 개의 셀에 칠해졌는지 알고자 합니다. 만약 여러 색상이 같은 최대 빈도를 보이면, 그 중 색상 번호가 가장 큰 것을 출력합니다.
[제한]
2 ≤ N ≤ 200\ 000 1 ≤ A_i ≤ 10^9 (1 ≤ i ≤ N )1 ≤ B_j ≤ 10^9 (1 ≤ j ≤ N )A_1 = B_1 주어지는 입력은 모두 정수.
입력
첫 번째 줄에 정수 N이 주어집니다.
두 번째 줄에 N개의 정수 A₁ A₂ … A_N (첫 번째 열의 색상)이 공백으로 구분되어 주어집니다.
세 번째 줄에 N개의 정수 B₁ B₂ … B_N (첫 번째 행의 색상)이 공백으로 구분되어 주어지며, A₁ = B₁임이 보장됩니다.
출력
한 줄에 두 개의 정수를 출력합니다.
첫 번째 정수는 최대로 많이 칠해진 색상의 번호이며, 두 번째 정수는 그 색상이 칠해진 셀의 개수입니다.
(여러 색상이 최대 빈도라면, 색상 번호가 가장 큰 것을 출력합니다.)
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 15점 | N ≤ 500, Aᵢ ≤ 10⁵ (1 ≤ i ≤ N), Bⱼ ≤ 10⁵ (1 ≤ j ≤ N). |
| #2 | 10점 | N ≤ 500 |
| #3 | 20점 | 모든 색상 Aᵢ, Bⱼ는 1 또는 2 |
| #4 | 25점 | A₁, A₂, …, A_N와 B₁, B₂, …, B_N가 각각 엄격히 증가함 |
| #5 | 30점 | 추가 제약 조건 없음 |
예제 #1
3
5 2 5
5 3 1
5 4
격자의 칠해진 모습은 다음과 같습니다.
5 3 1
2 3 3
5 5 5
색상 5가 4개의 셀(첫 행의 5, 셀(3,1), 셀(3,2), 셀(3,3))에 칠해져 있으며, 다른 색상들은 그보다 적게 칠해졌으므로, 출력은 "5 4"입니다.
예제 #2
3
1 7 8
1 3 5
8 3
격자의 칠해진 모습은 다음과 같습니다.
1 3 5
7 7 7
8 8 8
색상 7와 8이 각각 3개의 셀에 칠해지지만, 둘 중 색상 번호가 더 큰 8을 출력합니다.
예제 #3
4
2 1 2 1
2 1 1 2
2 10
로그인해야 코드를 작성할 수 있어요.