提出 #76711763

---

ソースコード 拡げる

class DSU:
    def __init__(self,n):
      self.parent=list(range(n))
      self.size=[0]*n
      self.total=0
    def find(self,x):
      while self.parent[x]!=x:
        self.parent[x]=self.parent[self.parent[x]]
        x = self.parent[x]
      return x
    def act(self,i,n):
      if self.size[i]>0:
        return 
      self.size[i]=1
      if i>0:
        left=self.find(i-1)
        if self.size[left]>0:
          self.merge(i,left)
      if i<n-1:
        right=self.find(i+1)
        if self.size[right]> 0:
          self.merge(i,right)
    def merge(self,a,b):
      ra=self.find(a)
      rb=self.find(b)
      if ra==rb:
        return
      self.total-=self.size[ra]*(self.size[ra]+1)//2
      self.total-=self.size[rb]*(self.size[rb]+1)//2
      self.parent[rb]=ra
      self.size[ra]+=self.size[rb]
      self.total+=self.size[ra]*(self.size[ra]+1)//2
def solve():
    N,Q,K=map(int,input().split())
    A=[]
    D=[]
    for _ in range(N):
      a,d=map(int,input().split())
      A.append(a)
      D.append(d)
    q=[]
    for i in range(Q):
      T=int(input())
      q.append((T,i))
    dark=[]
    for i in range(N):
      if A[i]<=K:
        dark.append((0,i))
      elif D[i]==0:
        dark.append((10**18,i))
      else:
        t=(A[i]-K+D[i]-1)//D[i]
        dark.append((t,i))
    dark.sort()
    q.sort()
    dsu=DSU(N)
    ans=[0]*Q
    p=0
    for T,idx in q:
      while p<N and dark[p][0]<=T:
        _,i=dark[p]
        dsu.act(i,N)
        p+=1
      ans[idx]=dsu.total
    for x in ans:
      print(x)
solve()

提出情報

ジャッジ結果