ABC080 D. Recording
Difficulty:1383
問題
録画したい番組がN個ある。それぞれの番組は開始時刻$ Sと終了時刻$ Tが決まっている。最大でいくつの番組を同時に録画することになるか？
解法
上記問題概要では省略したが、録画する際に
同じチャンネルなら、$ S-1に録画をしていてもOK
別のチャンネルなら、$ S-1に録画をしていたらNG
という制約がある。そこで、チャンネルごとに処理してから全体を計算するとよい。
ある時刻にいくつの番組が存在するかというのは、imos法の考え方を使うことでBITに載せることができるほか、イベントソートで求めることもできる。今回は実装が簡単なBIT解法を採用した。
実装
code:cpp
bool solve(){
LL(n,c);
vector<fenwick_tree<ll>>seg(c,fenwick_tree<ll>(100005));
rep(i,n){
LL(s,t,c);c--;
}
ll ans{};
rep(i,100004){
rep(j,c){
}
}
}
rep(i,100005){
ll cn{};
rep(j,c){
}
chmax(ans,cn);
}
O(ans);
return false;
}