問題一覧 > 通常問題

No.1995 CHIKA Road

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 114
作問者 : MasKoaTSMasKoaTS / テスター : Kanten4205Kanten4205 potato167potato167
8 ProblemId : 7734 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-04 23:53:58

問題文

コウメ市には $1, 2, \dots, N$ の番号が付いた $N$ 個の町があり、
これらは次に示す $(N - 1)$ 本の「地下道」と $M$ 本の「近道」で一方向に結ばれています。

  • $i$ $(1 \leq i \leq N - 1)$ 本目の「地下道」は町 $i$ と町 $(i + 1)$ をこの順に結び、その間の距離は $2$ である。

  • $j$ $(1 \leq j \leq M)$ 本目の「近道」は町 $A_{j}$ と町 $B_{j}$ $(A_{j} < B_{j})$ をこの順に結び、その間の距離は $(2 B_{j} - 2 A_{j} - 1)$ である。

これら $(N + M - 1)$ 本の道のみを通過して町 $1$ から町 $N$ まで移動するとき、最短移動距離を求めてください。

制約

  • $2 \leq N \leq 10^{9}$

  • $\displaystyle 1 \leq M \leq \min \left( 10^{5}, \frac{ N \times (N - 1) }{ 2 } \right)$

  • $1 \leq A_{i} < B_{i} \leq N$ $(1 \leq i \leq M)$

  • $( A_{i}, B_{i} ) \neq ( A_{j}, B_{j} )$ $(1 \leq i < j \leq M)$

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$ $M$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
   $\vdots$
$A_{M}$ $B_{M}$
  • $1$ 行目には $N$ と $M$ がこの順に半角スペース区切りで与えられる

  • $(1 + i)$ $(1 \leq i \leq M)$ 行目には $A_{i}$ と $B_{i}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

サンプル1
入力
10 5
1 6
2 4
2 7
4 6
6 9
出力
15

町 $1$ から町 $10$ まで最短距離で移動するためには、次のような移動経路を考えれば良いです。

  1. 「地下道」を通過して町 $1$ から町 $2$ に移動

  2. 「近道」を通過して町 $2$ から町 $4$ に移動

  3. 「近道」を通過して町 $4$ から町 $6$ に移動

  4. 「近道」を通過して町 $6$ から町 $9$ に移動

  5. 「地下道」を通過して町 $9$ から町 $10$ に移動

よって、求める最短移動距離は

  $2 + (2 \times 4 - 2 \times 2 - 1) + (2 \times 6 - 2 \times 4 - 1) + (2 \times 9 - 2 \times 6 - 1) + 2 = 15$

となります。

サンプル2
入力
2 1
1 2
出力
1

町 $1$ と町 $2$ をこの順に結ぶ道は $2$ 本ありますが、
それぞれ「地下道」と「近道」で区別されていることに注意してください。

サンプル3
入力
1000000000 7
1 2
7 8
3 4
6 7
4 5
5 6
2 3
出力
1999999991

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。