Edited at

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$個の閉区間全てに共通する要素の個数を数え上げる問題。

実験すればわかるが、全ての区間が重なっているということは「最も左側にある右端」>=「最も右側にある左端」が成り立つ。(この問題は閉区間なので>=となる。)

よって、「最も左側にある右端」と「最も右側にある左端」を minmax で更新していき、右端-左端が正か負か判定します。正なら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;
}