Recording [AtCoder Beginner Contest 080 D]

https://beta.atcoder.jp/contests/abc080/tasks/abc080_d

前提知識

• imos法

解法

https://beta.atcoder.jp/contests/abc080/submissions/1831052

連続して流れる番組はまとめてしまう方が良い。
まとめる作業はちょっと後回しにして、まとめてあるとして問題を解いてみる。
　
ここでimos法を使う。
imos法を使ってチャンネルC[i]の[L[i],R[i]]に1を代入する。
テレビ番組は[L[i],R[i])で放送されるが、録画機の切り替えに時間が必要な事を考えると、[L[i],R[i]]だけ録画機を独占していることになるので、どちらも閉区間で塗る。
あとは、全ての時刻について録画機が使われているチャンネル数を数えて、その最大値が答え。
　
まとめる作業を考える。
まとめずに以上のようにimos法をすると、ダブっている区間が1ではなく2になる。
しかし、この部分は録画機を2台分使っているわけではないので、1になおしておこう。
この後処理を加えることで事前にまとめるのと同じ状況にしている。

int N, C;
int imos[30][101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> C;
    rep(i, 0, N) {
        int a, b, c; cin >> a >> b >> c;
        a--; c--;
        imos[c][a]++;
        imos[c][b]--;
    }
    rep(c, 0, C) rep(i, 1, 101010) imos[c][i] += imos[c][i - 1];
    rep(c, 0, C) rep(i, 0, 101010) if (imos[c][i]) imos[c][i] = 1;
 
    int ans = 0;
    rep(i, 0, 101010) {
        int cnt = 0;
        rep(c, 0, C) cnt += imos[c][i];
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}