問題一覧 > 通常問題

No.1557 Binary Variable

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

問題文

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

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

N 個のバイナリ変数 B1,B2,…,BN が ∑i=1M∏j=LiRiBj=0 を満たしているとき、 S=∑k=1NBk としてあり得る最大の値を求めてください。

制約

  • 入力はすべて整数
  • 1≤N≤109
  • 1≤M≤2×105
  • 1≤Li≤Ri≤N(1≤i≤M)
  • (Li,Ri)≠(Lj,Rj)(i≠j)

    • 入力

    N M
L1 R1
 ⋮⋮
LM RM

    出力

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

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

    サンプル

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

    (B1,B2,B3,B4,B5)=(1,1,0,1,1) とすれば条件を満たします。

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

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

    Li=Ri である可能性があります。

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

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