問題
정올국에는 '뚫기'라는 게임이 유행 중이다. 게임은 가로 길이 N, 세로 길이 M의 직사각형의 가장 왼쪽에서 시작하여, 비행선을 조종해 장애물을 뚫거나 피해서 끝까지 가면 된다.
장애물은 세로 모양의 선분으로 표현할 수 있으며, 가로를 x축, 세로를 y축이라고 했을 때 한 x좌표에 최대 하나의 장애물만 있다.
여러분의 비행선은 기본적으로 +x축 방향으로 움직이고 있다. 장애물을 피하기 위해 세로 방향으로 움직일 수 있는데, 이떄 움직인 위치와 거리와는 상관없이 항상 A만큼의 연료를 사용한다. 또, B만큼의 연료를 사용하여 장애물을 뚫고 지나갈 수도 있다.
여러분의 목표는 모든 장애물을 지나 직사각형의 가장 오른쪽으로 가는 것이다. 최소한의 연료를 사용하여 목표를 달성해보자.
하지만 A와 B의 값은 그날그날 비행선의 상태에 따라 달라지기 때문에, 총 Q개의 A와 B쌍이 주어졌을 때 각각에 대한 최소 연료를 구해보자.
入力
첫 줄에 직사각형의 크기를 나타내는 변수 N, M과 쿼리의 개수 Q가 주어진다.
1<=N<=10000, 1<=M<=10^9, 1<=Q<=10^6을 만족한다.
그 이후 N개의 줄에 걸쳐 i번째 줄에는 x=i 일때의 장애물의 위치를 나타내는 변수 y1, y2가 주어진다.
0<=y1<=y2<M이고, 이는 (i, y1)과 (i, y2+1) 사이를 잇는 선분 모양의 장애물을 뜻한다.
그 이후 Q개의 줄에 걸쳐 A와 B의 쌍이 주어진다.
0<=A, B<=10^9를 만족한다.
出力
각 쿼리마다 목표를 달성하는데 필요한 최소 연료를 한 줄에 하나씩 출력하시오.
部分問題
| 番号 | 点数 | 条件 |
|---|---|---|
| #1 | 7点 | Q=1, N<=3000, M<=3000 |
| #2 | 22点 | Q<=50 |
| #3 | 19点 | N<=500 |
| #4 | 21点 | N<=2500 |
| #5 | 31点 | 추가 제한 없음 |
例題
3 5 2
2 4
0 2
1 3
2 1
3 5
1
3
ログインしないとコードを書けません。