結果

問題 No.1079 まお
ユーザー sasa8uyauya
提出日時 2025-02-25 12:48:37
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,984 bytes
コンパイル時間 678 ms
コンパイル使用メモリ 82,068 KB
実行使用メモリ 308,292 KB
最終ジャッジ日時 2025-02-25 12:49:08
合計ジャッジ時間 30,325 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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.L=1<<(len(bin(n))-2)
    self.st=[0]*self.L*2
    return
  
  def add(self,p,x):
    p+=self.L
    self.st[p]+=x
    p//=2
    while p>0:
      self.st[p]+=x
      p//=2
    return
  
  def sum(self,l,r):
    if l>r:
      return 0
    l+=self.L
    r+=self.L
    pl=[]
    pr=[]
    while l<=r:
      if l%2==1:
        pl+=[l]
        l+=1
      if r%2==0:
        pr+=[r]
        r-=1
      l//=2
      r//=2
    if len(pl)>0 and len(pr)>0 and pr[-1]==pl[-1]:
      pr.pop()
    a=sum(self.st[i] for i in pl+pr[::-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