| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 80 | 26 | 22 | 31.429% |
길이가 $N-1$인 수직선이 있다. 수직선 위의 $1$에서 시작하여 $N$에 가능한 한 빠르게 도달하는 것이 목표이다.
시각 $0$분에 시작해서 매 분마다 $1$분에 걸쳐 다음 세 행동 중 하나를 할 수 있다.
단, 이동한 뒤의 위치는 항상 $1$ 이상 $N$ 이하여야 한다. $N$에 도착하는 즉시 성공한 것으로 간주한다.
$1$분부터 $T$분까지 총 $T$분 동안 매 분마다 통제가 발생한다. $t$분의 통제는 두 정수 $l_t, r_t$로 주어지며, 시각 $t$분에 이동을 모두 마친 직후 당신의 위치 $x$가 $l_t \le x \le r_t$를 만족하면 즉시 실패한다. $T < t$인 경우에는 통제가 발생하지 않는다.
실패하지 않고 $N$에 도착하는 방법이 존재한다면 가능한 최단 시간을 출력하고, 존재하지 않으면 -1을 출력하시오.
첫 번째 줄에 도착 지점 $N$이 주어진다. $(1 \le N \le 2 \times 10^5)$
두 번째 줄에 통제가 발생하는 총 시간 $T$가 주어진다. $(1 \le T \le 2 \times 10^5)$
세 번째 줄부터 $T$개의 줄에 걸쳐 각 줄에 두 정수 $l_t$, $r_t$가 공백으로 구분되어 주어진다.$(1 \le l_t \le r_t \le N)$
실패하지 않고 좌표 $N$에 도달할 수 있다면 가능한 최단 시간을 출력한다.
그러한 방법이 존재하지 않으면 -1을 출력한다.
4 4 2 4 1 1 2 2 3 3
4
5 3 2 5 3 4 1 4
-1
School > 한국디지털미디어고등학교 > 제4회 디미고 프로그래밍 챌린지 I번