結果

問題 No.1079 まお
ユーザー sasa8uyauya
提出日時 2025-02-25 12:42:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,934 bytes
コンパイル時間 393 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 306,588 KB
最終ジャッジ日時 2025-02-25 12:42:53
合計ジャッジ時間 27,895 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,K=map(int,input().split())
a=list(map(int,input().split()))
z=sorted(set(a))
d={v:i for i,v in enumerate(z)}
g=0

class SegTree:
  def __init__(self,n):
    self.B=int(n**0.5)+1
    self.st1=[0]*self.B*self.B
    self.st2=[0]*self.B
    return
  
  def add(self,x,v):
    y=x//self.B
    self.st2[y]-=self.st1[x]
    self.st1[x]+=v
    self.st2[y]+=self.st1[x]
    return
  
  def sum(self,l,r):
    if l>r:
      return 0
    yl=l//self.B
    yr=r//self.B
    a=0
    if yl==yr:
      a+=sum(self.st1[l:r+1])
    else:
      a+=sum(self.st1[l:yl*self.B+self.B])
      a+=sum(self.st2[yl+1:yr])
      a+=sum(self.st1[yr*self.B:r+1])
    return a

sts=SegTree(len(d))
stc=SegTree(len(d))

def solve(l,r):
  global g
  if l==r:
    v=a[l]
    if v+v==K:
      g+=1
    return {v:[(1,v,1)]},{v:[(1,v,1)]}
  w=(r-l+1)//2
  ql,_=solve(l,l+w-1)
  _,qr=solve(l+w,r)
  for lv in ql:
    if K-lv in qr:
      for x,v,c in qr[K-lv]:
        y=d[v]
        sts.add(y,x)
        stc.add(y,1)
      for x,v,c in ql[lv]:
        if c==1:
          y=d[v]
          g+=x*stc.sum(y+1,len(d)-1)+sts.sum(y+1,len(d)-1)
      for x,v,c in qr[K-lv]:
        y=d[v]
        sts.add(y,-x)
        stc.add(y,-1)
  for rv in qr:
    if K-rv in ql:
      for x,v,c in ql[K-rv]:
        y=d[v]
        sts.add(y,x)
        stc.add(y,1)
      for x,v,c in qr[rv]:
        if c==1:
          y=d[v]
          g+=x*stc.sum(y+1,len(d)-1)+sts.sum(y+1,len(d)-1)
      for x,v,c in ql[K-rv]:
        y=d[v]
        sts.add(y,-x)
        stc.add(y,-1)
  ql={}
  mv=10**10
  c=1
  for i in reversed(range(l,r+1)):
    v=a[i]
    if v<mv:
      mv=v
      c=1
    elif v==mv:
      c+=1
    if v not in ql:
      ql[v]=[]
    ql[v]+=[(r-i+1,mv,c)]
  qr={}
  mv=10**10
  c=1
  for i in range(l,r+1):
    v=a[i]
    if v<mv:
      mv=v
      c=1
    elif v==mv:
      c+=1
    if v not in qr:
      qr[v]=[]
    qr[v]+=[(i-l+1,mv,c)]
  return ql,qr

solve(0,n-1)
print(g)
0