Age of the Grand Wizard

2 secs 1024 MB
KuonAyano's icon KuonAyano

解説

まず、長さ10610^6の数列 T=T= [0,0,....,0][0,0,....,0]を作り1iN1≦i≦Nとなるiiすべてに対して、Ci=0Ci=0ならkS1k∈S1「ここで、集合S1=[0,Ai1]S1=[0,Ai-1]U[Bi,106][Bi,10^6]とします」となる整数kk全てに対してTkTk11を足し、Ci=1Ci=1ならkS2k∈S2「ここで、集合S2=[Ai,Bi1]S2=[Ai,Bi-1]とします」となる整数kk全てに対してTkTk11を足します。 (問題の制約上、これは「imos法」と言う累積和の取り方を使わずにやるとTLEとなります)

そうすると、1i1061≦i≦10^6となる年齢iiはお師匠様答えTiTi個と整合性が取れます。なので、Ti=1061Ti=10^6-1となるiiのリストD1D1を作り、Ci=0Ci=0Ci=1Ci=1かで適切に場合分けしつつ二分探索する事で、この問題をO(NlogN)O(NlogN)で解くことができます。

ライター解(Python)