AtCoder ABC127 C - Prison(300点)

問題概要

問題のリンク

$N$ 枚の ID カードと $M$ 個のゲートがある。
$i$ 番目のゲートは $L_i,L_{i+1},...,R_i$ 番目の ID カードのうちどれか $1$ 枚を持っていれば通過できる。$1$ 枚だけで全てのゲートを通過できる ID カードは何枚あるか。

制約条件

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

考えたこと

$M$個の閉区間全てに共通する要素の個数を数え上げる問題。

実験すればわかるが、全ての区間が重なっているということは「最も左側にある右端」>=「最も右側にある左端」が成り立つ。（この問題は閉区間なので>=となる。）
よって、「最も左側にある右端」と「最も右側にある左端」を min と max で更新していき、右端-左端が正か負か判定します。正なら1を足し、負なら0が答え。

計算量は $O(M)$ です。

解答

c.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    int r = n;
    int l = 0;
    for(int i = 0; i < m; i ++) {
        int x,y; cin >> x >> y;
        l = max(l,x);
        r = min(r,y);
    }
    cout << (r-l>=0 ? r-l+1 : 0) << endl;
}