2025-ho-t1_Grid_Coloring (JOI JOI)
Time limit: 2 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: two pointers, binary search

# Grid Coloring

![](_page_0_Picture_0.jpeg)

The 24th Japanese Olympiad in Informatics (JOI 2024/2025)
Final Round
February 2, 2025 (Online)

President K is designing a pattern represented by a grid with *N* rows and *N* columns. To achieve this, he has decided to paint each cell with a color represented by an integer number. Let us refer to the cell in the *i*-th row (1 ≤ *i* ≤ *N*) and *j*-th column (1 ≤ *j* ≤ *N*) as cell (*i*, *j*).

Currently, the cells in the first column and first row are already painted. Specifically, cell (*i*, 1) (1 ≤ *i* ≤ *N*) is painted with color *A<sub>i</sub>* and cell (1, *j*) (1 ≤ *j* ≤ *N*) is painted with color *B<sub>j</sub>*. Note that *A*<sub>1</sub> = *B*<sub>1</sub>.

For the remaining unpainted cells, President K is going to paint them by the following procedure:

*   For each *i* = 2, 3, . . . , *N* in order, paint the cells in the *i*-th row as follows:
    *   For each *j* = 2, 3, . . . , *N* in order, paint cell (*i*, *j*) with the color that has the larger number between:
        *   The color of cell (*i* − 1, *j*), and
        *   The color of cell (*i*, *j* − 1).

If both colors have the same number, paint the cell with that color.

President K would like to determine the color that is painted on the largest number of cells after all *N*<sup>2</sup> cells have been painted, as well as the number of cells painted with that color.

Write a program that, given the size of the grid and the color information for the first column and first row, determines the color number painted on the largest number of cells and the number of cells painted with that color. If multiple colors are painted on the largest number of cells, output the largest color number among them.

### Input

Read the following data from the standard input.

```
N
A1 A2 · · · AN
B1 B2 · · · BN
```

### Output

Write one line to the standard output containing two integers separated by a space:

1.  The color number that is painted on the largest number of cells, and
2.  The number of cells painted with that color.

If multiple colors are painted on the largest number of cells, output the largest color number among them.

### Constraints

*   2 ≤ *N* ≤ 200 000.
*   1 ≤ *A<sub>i</sub>* ≤ 10<sup>9</sup> (1 ≤ *i* ≤ *N*).
*   1 ≤ *B<sub>j</sub>* ≤ 10<sup>9</sup> (1 ≤ *j* ≤ *N*).
*   *A*<sub>1</sub> = *B*<sub>1</sub>.
*   Given values are all integers.

### Subtasks

1.  (15 points) *N* ≤ 500, *A<sub>i</sub>* ≤ 100 000 (1 ≤ *i* ≤ *N*), *B<sub>j</sub>* ≤ 100 000 (1 ≤ *j* ≤ *N*).
2.  (10 points) *N* ≤ 500.
3.  (20 points) *A<sub>i</sub>* ≤ 2 (1 ≤ *i* ≤ *N*), *B<sub>j</sub>* ≤ 2 (1 ≤ *j* ≤ *N*).
4.  (25 points) *A<sub>i</sub>* < *A<sub>i+1</sub>* (1 ≤ *i* ≤ *N* − 1), *B<sub>j</sub>* < *B<sub>j+1</sub>* (1 ≤ *j* ≤ *N* − 1).
5.  (30 points) No additional constraints.

### Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :-------------- |
| 3              | 5 4             |
| 5 2 5          |                 |
| 5 3 1          |                 |

In this sample, the color of each cell in the grid will be as follows:

|   |   |   |
| :-- | :-- | :-- |
| 5 | 3 | 1 |
| 2 | 3 | 3 |
| 5 | 5 | 5 |

The color number painted on the largest number of cells is 5, which appears on 4 cells. Thus, print 5 and 4 in this order, separated by a space.

This sample input satisfies the constraints of Subtasks 1, 2, and 5.

| Sample Input 2 | Sample Output 2 |
| :------------- | :-------------- |
| 3              | 8 3             |
| 1 7 8          |                 |
| 1 3 5          |                 |

In this sample, the color of each cell in the grid will be as follows:

|   |   |   |
| :-- | :-- | :-- |
| 1 | 3 | 5 |
| 7 | 7 | 7 |
| 8 | 8 | 8 |

The color numbers painted on the largest number of cells are 7 and 8, each painted on 3 cells. In this case, output the larger color number, 8, followed by the number of cells, 3, separated by a space.

This sample input satisfies the constraints of Subtasks 1, 2, 4, and 5.

| Sample Input 3 | Sample Output 3 |
| :------------- | :-------------- |
| 4              | 2 10            |
| 2 1 2 1        |                 |
| 2 1 1 2        |                 |

This sample input satisfies the constraints of Subtasks 1, 2, 3, and 5.

Task 1-3/3

Starter code:

Grader code:

Setup script:

Evaluation script: