結果

問題 No.1079 まお
ユーザー sasa8uyauya
提出日時 2025-02-25 12:33:35
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,457 bytes
コンパイル時間 853 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 123,652 KB
最終ジャッジ日時 2025-02-25 12:33:41
合計ジャッジ時間 5,980 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 30
権限があれば一括ダウンロードができます

ソースコード

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

from atcoder import fenwicktree
sts=fenwicktree.FenwickTree(len(d))
stc=fenwicktree.FenwickTree(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))+sts.sum(y+1,len(d))
      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))+sts.sum(y+1,len(d))
      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