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

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

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

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

問題概要

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

 t = 0, 1, \dots, T-1 について、時刻  t + 0.5 に何人の従業員が働いているかを求めよ。

制約

  •  1 \le N, T \le 5 \times 10^{5}

解法

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