問題一覧 > 通常問題

No.1557 Binary Variable

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 152
作問者 : noya2noya2 / テスター : nok0nok0 magstamagsta
6 ProblemId : 6279 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-16 00:30:06

問題文

$0$ または $1$ のいずれかの整数値をとる変数をバイナリ変数と言います。

正整数 $N,M$ と、$M$ 個の正整数の組が与えられます。$i$ 個目の組は $(L_i,R_i)$ です。

$N$ 個のバイナリ変数 $B_1,B_2,\dots ,B_N$ が $\displaystyle\sum_{i=1}^{M} \prod_{j=L_i}^{R_i} B_j = 0$ を満たしているとき、 $\displaystyle S=\sum_{k=1}^{N} B_k$ としてあり得る最大の値を求めてください。

制約

  • 入力はすべて整数
  • $1\le N \le 10^9$
  • $1\le M \le 2\times 10^5$
  • $1\le L_i \le R_i \le N\quad (1\le i\le M)$
  • $(L_i,R_i) \neq (L_j,R_j) \quad (i\neq j)$

    • 入力

    $N\ M$
$L_1\ R_1$
$\ \vdots \quad \vdots$
$L_M\ R_M$

    出力

    $S$ としてあり得る最大の値を出力してください。

    最後に改行してください。

    サンプル

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

    $(B_1,B_2,B_3,B_4,B_5)=(1,1,0,1,1)$ とすれば条件を満たします。

    このとき $S=4$ で、これより大きくすることはできないので $4$ を出力します。

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

    $L_i=R_i$ である可能性があります。

    サンプル3
    入力
    11 7
1 4
3 7
2 5
5 9
7 8
3 3
10 11
    出力
    8

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