17676번 - 시간을 달리는 비타로 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 34 | 12 | 12 | 36.364% |
문제
비버랜드에는 $N$개의 도시가 있다. 이 도시들은 1번부터 $N$번까지 번호가 붙어있다. $i$번째 ($1 \le i \le N-1$) 도로는 $i$번 도시와 $i+1$번 도시를 양방향으로 잇는다. 또한, 비버랜드의 하루는 1 000 000 000개의 단위시간으로 분열되어 있고, 이 단위시간을 쵸라고 부른다. 하루가 시작하고 나서 $x$쵸가 지난 시간을 시각 $x$라 부른다. 한 도로를 통과하는 데에는 1쵸가 걸리고, $i$번째 도로는 시각 $L_i$와 시각 $R_i$ 사이에만 통과할 수 있다. 구체적으로, $i$번째 도로를 통과하기 위해서 우리는 도시 $i$나 $i+1$을 $L_i \le x \le R_i -1$ 을 만족하는 시각 $x$에 떠나야 하고, 다른 도시에 시각 $x+1$에 도착해야 한다.
비타로는 비버랜드에 사는 평범한 비버다. 아니, 비버였다 라고 하는게 옳은 것일까. 지각을 자주한 비타로는 이를 개선하려고 한 결과로 시간을 거슬러 올라가는게 가능해 졌다. 이 능력을 한 번 사용하면 1쵸 뒤로 갈 수 있다. 하지만, 어제로 갈 수는 없다. 만약 그가 능력을 시각 0과 시각 1 사이에 사용했다면, 그는 시각 0으로 돌아갈 것이다. 그는 이 기술을 도시에 있을 때 사용할 수 있다. 비타로의 위치는 능력을 사용해도 변하지 않는다.
비타로는 기술을 사용하면 피곤해 진다. 최소한의 기술을 사용하여 이동하는 방법을 찾기 위한 비타로는 $Q$개의 사고실험을 진행했다. 사고 실험의 $j$ 번째 단계에서는, 그는 다음 중 한 행동을 한다:
- $P_j$ 번째 도로가 여행될수 있는 시각을 바꾼다. 바뀐 이후에는, 시각 $S_j$와 시각 $E_j$ 사이에만 $P_j$ 번째 도로를 통과할 수 있다.
- 그가 $A_j$번 도시, 시각 $B_j$에 있다고 할 때, $C_j$번 도시, 시각 $D_j$로 이동하기 위해 사용해야하는 능력의 수의 최솟값을 구하여라.
그는 사고실험의 결과를 궁금해한다.
비버랜드의 도시의 수, 도로의 정보, 사고실험의 방법이 주어졌을 때, 사고 실험의 결과를 계산하는 프로그램을 작성하여라.
입력
표준 입력에서 다음과 같은 형식으로 주어진다. 모든 값은 정수이다.
$N$ $Q$
$L_1$ $R_1$
$\vdots$
$L_{N-1}$ $R_{N-1}$
(Query 1)
$\vdots$
(Query $Q$)
여기서, (Query $j$)는 공백으로 구분된 4개나 5개의 정수로 이루어져 있다. $T_j$가 첫 번째 정수라고 하자. 그러면,
- $T_j=1$인 경우, (Query $j$)는 4개의 정수 $T_j$, $P_j$, $S_j$, $E_j$로 이루어져 있다. 이것은, 사고 실험의 $j$번째 단계에서, $P_j$번째 도로를 지날수 있는 시간이 시각 $S_j$와 시각 $E_j$ 사이로 바뀐다는 것을 의미한다.
- $T_j=2$인 경우, (Query $j$)는 5개의 정수 $T_j$, $A_j$, $B_j$, $C_j$, $D_j$로 이루어져 있다. 이는, $j$번째 사고 실험에서, 당신의 프로그램이 비타로가 $A_j$번 도시, 시각 $B_j$에 있다고 할 때, $C_j$번 도시, 시각 $D_j$로 이동하기 위해 사용해야하는 능력의 수의 최솟값을 구해야 한다는 것을 의미한다.
출력
$T_j=2$인 각 단계에 대해서, 사용해야 하는 능력의 수의 최솟값을 한 줄에 하나씩 차례로 출력하여라.
제한
- $1 \le N \le 300\ 000$.
- $1 \le Q \le 300\ 000$.
- $0 \le L_i < R_i \le 999\ 999\ 999$ ($q \le i \le N-1$).
- $1 \le T_j \le 2$ ($1 \le j \le Q$).
- $1 \le P_j \le N-1$ ($1 \le j \le Q$, $T_j = 1$).
- $1 \le S_j \le E_j \le 999\ 999\ 999$ ($1 \le j \le Q$, $T_j = 1$).
- $1 \le A_j \le N$ ($1 \le j \le Q$, $T_j = 2$).
- $1 \le B_j \le 999\ 999\ 999$ ($1 \le j \le Q$, $T_j = 2$).
- $1 \le C_j \le N$ ($1 \le j \le Q$, $T_j = 2$).
- $1 \le D_j \le 999\ 999\ 999$ ($1 \le j \le Q$, $T_j = 2$).
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | N ≤ 1000, Q ≤ 1000. |
| 2 | 30 | Tj = 2 (1 ≤ j ≤ Q). |
| 3 | 66 | No additional constraints. |
예제 입력 1
3 3 0 5 0 5 2 1 3 3 3 1 2 0 1 2 1 3 3 3
예제 출력 1
2 4
사고 실험의 첫 번째 단계에서, 비타로는 1번 도시에서 2번 도시로 1쵸만에 이동하고, 2번 도시에서 3번 도시로 1쵸만에 이동하여 3번 도시, 시각 5에 위치하여 있다. 능력을 두번 사용하면, 그는 3번 도시, 시각 3에 위치할 수 있다.
사고 실험의 두 번째 단계에서, 2번 도시를 통과할 수 있는 시간이 시각 0부터 시각 1까지로 바뀐다.
사고 실험의 세 번째 단계에서, 1번 도시에서 2번 도시로 1쵸 만에 이동하여, 2번 도시, 시각 4에 위치해 있다. 여기서 능력을 네 번 사용하면, 3번 도시로 1쵸만에 이동하여 2쵸를 기다리면 3번 도시, 시각 3에 위치할 수 있다.
예제 입력 2
5 5 3 5 4 8 2 6 5 10 2 5 3 1 10 2 2 6 5 6 1 3 4 6 2 3 3 4 3 2 4 5 1 5
예제 출력 2
4 3 2 3
예제 입력 3
7 7 112103440 659752416 86280800 902409187 104535475 965602300 198700180 945132880 137957976 501365807 257419446 565237610 2 4 646977260 7 915994878 2 1 221570340 6 606208433 2 7 948545948 4 604273995 2 7 247791098 5 944822313 2 7 250362511 2 50167280 2 3 364109400 4 555412865 2 7 33882587 7 186961394
예제 출력 3
145611455 0 447180143 0 207252171 0 0
예제 입력 4
7 7 535825574 705426142 964175291 996597835 481817391 649559926 4519006 410772613 74521477 274584126 256535565 899389890 1 6 511428966 602601933 1 1 69986642 201421232 2 3 636443425 4 625975977 1 6 235225515 405336399 2 3 866680458 3 701821857 1 6 180606048 900533151 1 6 612564160 720179605
예제 출력 4
10467449 164858601
출처
Camp > JOI Spring Training Camp > JOI 2018/2019 Spring Training Camp 3-3번
- 문제를 번역한 사람: ho94949
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호