けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 014 C - AtColor (水色)

いもす法の典型問題

問題概要

サイズ 1000001 の配列 v が与えられる (index は、0, 1, ..., 1000000)。

以下の  N 回の操作を行う。

  •  i 回目の操作では、 a_{i} \le x \le b_{i} を満たす  x について、v[x] に 1 を加算する

すべての操作を行ったあとの、配列中の値の最大値を求めよ。

制約

  •  1 \le N \le 10^{5}

考えたこと

完全にいもす法そのものな問題。いもす法のやり方は、次の資料などを。

drken1215.hatenablog.com

この ABC 183 C 問題は、今回の問題の上位互換的な問題になっている。いもす法を使うと、配列 v が求められるので、その最大値を求めれば OK。

コード

計算量は  A = 1000001 として、 O(N + A) になる。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;

    int A = 1000001;
    vector<int> v(A + 1, 0);
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        v[a]++;
        v[b+1]--;
    }
    for (int i = 0; i <= A; ++i) v[i+1] += v[i];

    int res = 0;
    for (int i = 0; i <= A; ++i) res = max(res, v[i]);
    cout << res << endl;
}