鉄則本 B07 - Convenience Store 2 (3Q, ★3)

これは A07 と大体一緒ですね！

• 問題へのリンク

問題概要

あるコンビニは時刻 0 に開店し、時刻 に閉店する。 人の従業員が働いていて、従業員 は時刻 に出勤して、時刻 に退勤する。

について、時刻 に何人の従業員が働いているかを求めよ。

制約

• 

解法

github.com

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int D, N;
    cin >> D >> N;
    
    // バケットの準備
    vector<int> bac(D + 1, 0);
    
    // いもす法の準備
    for (int i = 0; i < N; ++i) {
        int L, R;
        cin >> L >> R;
        
        // 区間 [L, R) への加算は、差分をとると「L への加算」「R への減算」となる
        ++bac[L];
        --bac[R];
    }
    
    // 最後に累積和をとる
    for (int d = 0; d < D; ++d) {
        bac[d + 1] += bac[d];
    }
    
    // 出力
    for (int d = 0; d < D; ++d) {
        cout << bac[d] << endl;
    }
}