AtCoder ABC 014 C - AtColor (試験管水色)

人生で最初に解きたい、いもす法の練習問題！

• 問題へのリンク

問題概要

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

以下の 回の操作を行う。

• 回目の操作では、 を満たす について、v[x] に 1 を加算する

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

制約

• 

考えたこと

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

drken1215.hatenablog.com

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

コード

計算量は として、 になる。

#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;
}