問題一覧 > 通常問題

No.1557 Binary Variable

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 164
作問者 : noya2 / テスター : nok0 magsta
お気に入りにしたユーザー ProblemId : 6279 / 自分の提出
問題文最終更新日: 2021-05-16 00:30:06
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 301 (順位表) の他の問題:

Problem Statement

A variable that takes an integer value of either $0$ or $1$ is called a binary variable.

You are given positive integers $N,M$ and $M$ pairs of positive integers. The $i$-th pair is $(L_i,R_i)$.

When $N$ binary variables $B_1,B_2,\dots ,B_N$ satisfy $\displaystyle\sum_{i=1}^{M} \prod_{j=L_i}^{R_i} B_j = 0$, find the maximum possible value of $\displaystyle S=\sum_{k=1}^{N} B_k$.

Constraints

  • All inputs are integers.
  • $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)$

    • Input

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

    Output

    Output the maximum possible value of $S$.

    Print a newline at the end.

    Sample

    Sample 1
    Input
    5 2
1 3
3 5
    Output
    4

    Setting $(B_1,B_2,B_3,B_4,B_5)=(1,1,0,1,1)$ satisfies the condition.

    In this case $S=4$, and it cannot be made larger than this, so output $4$.

    Sample 2
    Input
    3 4
1 1
1 2
2 3
3 3
    Output
    1

    It is possible that $L_i=R_i$.

    Sample 3
    Input
    11 7
1 4
3 7
2 5
5 9
7 8
3 3
10 11
    Output
    8

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