벚꽃 엔딩

면접 대비

시간 제한3초메모리 제한1024 MB

요약

N그루 벚나무의 개화 기간이 주어질 때, 하루 중 인접한 나무가 연속으로 모두 꽃이 핀 최대 길이와 그 길이가 나오는 날의 수를 구합니다.

난이도: 보통10점 중 6점
유형: 세그먼트 트리, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

출처: 윤찐빵

UDP 마을에서 UDPC를 기념하는 벚꽃 축제가 열렸다! 축제는 $M$ 일 동안 열리며, 축제 장소에는 나무 $N$ 그루가 일렬로 서 있다. 나무에는 순서대로 1번부터 $N$ 번까지 번호가 붙어 있다. $i$ 번째 벚나무에는 축제의 $S_i$ 번째 날부터 $E_i$ 번째 날까지 벚꽃이 핀다. 벚꽃은 모여 있을수록 예쁘므로, 윤이, 달구, 포닉스는 가장 많은 벚나무가 일렬로 연속해서 피어 있는 날에 꽃구경을 가려 한다. 어떤 날에 $a$ 번 나무부터 $b$ 번 나무까지 일렬로 연속해서 피어 있다는 것은, 그날 $a$ 번 나무부터 $b$ 번 나무까지 모두 벚꽃이 피어 있다는 뜻이다. 또 어떤 날에 일렬로 연속해서 핀 벚나무의 개수는 이러한 구간 $[a, b]$ 중 길이 $b-a+1$ 의 최댓값이다. 축제를 기대하는 세 마스코트를 위해 축제 기간 중 일렬로 연속해서 핀 벚나무 개수의 최댓값과, 가장 많은 벚나무가 일렬로 연속해서 핀 날의 개수를 구해 보자!

입력

첫 번째 줄에 벚나무의 개수 $N$ 과 축제 기간 $M$ 이 공백으로 구분되어 주어진다. ( $1\leq N\leq 10^5;1\leq M\leq 10^9$ )

두 번째 줄부터 $N$ 줄에 걸쳐 $i+1$ 번째 줄에 $i$ 번째 벚나무에 벚꽃이 피는 기간을 나타내는 $S_i$ 와 $E_i$ 가 공백으로 구분되어 순서대로 주어진다. ( $1\leq S_i\leq E_i\leq M$ )

출력

축제 기간 중 일렬로 연속해서 핀 벚나무 개수의 최댓값과, 가장 많은 벚나무가 일렬로 연속해서 핀 날의 개수를 공백으로 구분하여 순서대로 출력한다.

예제3

예제 1
입력
```
3 5
3 5
1 3
1 1
```
예상 출력
```
2 2
```
예제 2
입력
```
5 10
8 10
6 9
1 3
5 9
1 8
```
예상 출력
```
2 5
```
예제 3
입력
```
3 3
1 1
2 2
3 3
```
예상 출력
```
1 3
```