AtCoder Beginner Contest 305 ABC D - Sleep Logの勉強

atcoder.jp

・参考：
Submission #42147989 - KYOCERA Programming Contest 2023（AtCoder Beginner Contest 305）

・考え方：前処理をしてクエリの中の処理を軽くする。二分探索を使うのでスライスにおけるAのi番目までの睡眠時間を前処理として行えば良い。プログラムの処理1では二分探索の位置が偶数だとansを引きすぎたり足しすぎたりしているのでそれを処理する。

・実装例：

import bisect
n=int(input())
a=list(map(int,input().split()))

　　　　　　　　　　　　　　　　　　　　　　　　　#前処理。

#aに対応した睡眠時間をa_tにいれる。例えばはじめのテストケースで考えるとaのはじめからaの3番目(スライスにおける)までの睡眠時間はa_t[3]=480分。
a_t=[0]
t=0
for i in range(1,n):
  if i%2==0:
    t+=a[i]-a[i-1]
    a_t.append(t)
  else:
    a_t.append(t)
#print(a_t)   #はじめのケースで[0, 0, 480, 480, 600, 600, 960]

q=int(input())
for _ in range(q):
  l,r=map(int,input().split())
  s=bisect.bisect_left(a,l)
  g=bisect.bisect_left(a,r)



  　　　　　　　　　　　　　　　　　　　　　　　　#処理1

  ans=a_t[g]-a_t[s]   #sからgまでの暫定的な睡眠時間。ただしsが偶数だと例えばl=250,s=2ではa_t[2]=480となり引きすぎてしまうので480-250の引きすぎた分を足す必要がある。gが偶数だと逆に足しすぎているので引く必要がある。
  #print(s,g,a_t[s],a_t[g],ans)
  if s%2==0:
    ans+=a[s]-l    #例えば、はじめのテストケースa[s]=a[2]=720でa_t[s]-l=720-480が引きすぎた睡眠時間になる。
  if g%2==0:
    ans-=a[g]-r    #例えばｒが1920,g=6だとa[6]-r=2160-1920=240を引けばよい。
  print(ans)