27927번 - 벚꽃 엔딩 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 264 | 72 | 63 | 37.725% |
문제
출처: 윤찐빵
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$)
출력
축제 기간 중 일렬로 연속해서 핀 벚나무 개수의 최댓값과, 가장 많은 벚나무가 일렬로 연속해서 핀 날의 개수를 공백으로 구분하여 순서대로 출력한다.
예제 입력 1
3 5 3 5 1 3 1 1
예제 출력 1
2 2
예제 입력 2
5 10 8 10 6 9 1 3 5 9 1 8
예제 출력 2
2 5
예제 입력 3
3 3 1 1 2 2 3 3
예제 출력 3
1 3
출처
University > UNIST-DGIST-POSTECH > 2023 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2023 UDPC) J번
- 문제를 검수한 사람: 99asdfg, cs71107, hyperbolic, kdh9949, knon0501, queued_q, slah007, tony9402, utilforever
- 문제를 만든 사람: leo020630
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호