問題一覧 > 通常問題

No.1557 Binary Variable

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 117
作問者 : 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もしくは右上の雲マークをクリックしてアカウントを作成してください。