問題一覧 > 通常問題

No.1244 Black Segment

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 76
作問者 : tute7627tute7627 / テスター : tempura_pptempura_pp
23 ProblemId : 3952 / 出題時の順位表
問題文最終更新日: 2020-10-03 00:47:21

問題文

$N$ 個のセルが横一列に並んでおり、セルには左から順に $1$ から $N$ の番号がついています。
最初、全てのセルは白く塗られています。
あなたは番号 $A,B$ のセル $(A \le B)$ をどちらも含むある一区間のみのセルを黒く塗りたいです。
正確には、以下の条件を満たすような整数 $X,Y$ の組み合わせが存在するような状態にする必要があります。

  • $X \le A \le B \le Y$
  • $X$ 以上 $Y$ 以下の番号がついたセルは黒く塗られており、それ以外のセルは白く塗られている。
$M$ 個のボタンがあり、$i$ 個目のボタンを押すと $L_i$ 以上 $R_i$ 以下の番号がついたセルの白と黒が反転します。
あなたは任意の順番で任意の回数ボタンを押すことができます。
セルが条件を満たすようにするためにボタンを押す最小の回数を求めてください。

入力

$N\ M\ A\ B$
$L_1\ R_1$
$L_2\ R_2$
$\vdots$
$L_M\ R_M$

  • 入力は全て整数である。
  • $1 \le N \le 10^5$
  • $1 \le M \le 10^5$
  • $1 \le A \le B \le N$
  • $1 \le L_i \le R_i \le N$

出力

ボタンを押す回数の最小値を出力してください。
条件を満たすことが不可能な場合は -1 を出力してください。
最後に改行してください。

サンプル

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

$3$ 個目のボタンを押すことで条件が満たされます。
最小の回数にはなりませんが、$1$ 個目のボタン、$2$ 個目のボタンをこの順で押すことでも条件を満たせます。

サンプル2
入力
5 3 2 4
1 3
3 5
1 1
出力
-1

どのようにボタンを押しても条件を満たすことはありません。

サンプル3
入力
5 5 1 5
1 3
3 5
2 2
4 4
2 4
出力
5

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