0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

AtCoder ABC127 C - Prison(300点)

Last updated at Posted at 2019-05-26

#問題概要
問題のリンク

$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;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?