解説
まず、長さ106の数列 T= [0,0,....,0]を作り1≦i≦Nとなるiすべてに対して、Ci=0ならk∈S1「ここで、集合S1=[0,Ai−1]U[Bi,106]とします」となる整数k全てに対してTk
に1を足し、Ci=1ならk∈S2「ここで、集合S2=[Ai,Bi−1]とします」となる整数k全てに対してTkに1を足します。
(問題の制約上、これは「imos法」と言う累積和の取り方を使わずにやるとTLEとなります)
そうすると、1≦i≦106となる年齢iはお師匠様答えTi個と整合性が取れます。なので、Ti=106−1となるiのリストD1を作り、Ci=0かCi=1かで適切に場合分けしつつ二分探索する事で、この問題をO(NlogN)で解くことができます。
ライター解(Python)