Atcoder解いてみた AtCoder Beginner Contest C - AtColor

AtCoder Beginner Contest C - AtColor

問題はこちら

回答

一次元いもす法の練習

#include <limits.h>

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>

int N;
std::vector<int> arrSum;

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);

    std::cin >> N;

    arrSum.resize(1000100);
    for (int i = 0; i < N; i++) {
        int a, b;
        std::cin >> a >> b;
        b++;  // [a,b)

        arrSum[a]++;
        arrSum[b]--;
    }

    for (int i = 1; i < arrSum.size(); i++) {
        arrSum[i] += arrSum[i - 1];
    }

    int ans = -1;
    for (int i = 0; i < arrSum.size(); i++) {
        ans = std::max(ans, arrSum[i]);
    }

    std::cout << ans << std::endl;

    return 0;
}