結果

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

ソースコード

diff # 

n,K=map(int,input().split())
a=list(map(int,input().split()))
g=0

def solve(l,r):
  global g
  if l==r:
    v=a[l]
    if v+v==K:
      g+=1
    return [(v,v)],[(v,v)]
  w=(r-l+1)//2
  ql,_=solve(l,l+w-1)
  _,qr=solve(l+w,r)
  qrs={}
  qrc={}
  qrsx={}
  qrcx={}
  for i in range(len(qr)):
    rv,mv=qr[i]
    if rv==-1:
      continue
    if rv not in qrs:
      qrs[rv]=0
      qrc[rv]=0
      qrsx[rv]={}
      qrcx[rv]={}
    qrs[rv]+=i+1
    qrc[rv]+=1
    if mv not in qrsx[rv]:
      qrsx[rv][mv]=0
      qrcx[rv][mv]=0
    qrsx[rv][mv]+=i+1
    qrcx[rv][mv]+=1
  for i in range(len(ql)):
    lv,mv=ql[i]
    if lv==-1:
      continue
    if K-lv in qrs:
      g+=(i+1)*qrc[K-lv]+qrs[K-lv]
      if mv in qrsx[K-lv]:
        g-=(i+1)*qrcx[K-lv][mv]+qrsx[K-lv][mv]
  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 c==1:
      ql+=[(v,mv)]
    else:
      ql+=[(-1,-1)]
  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 c==1:
      qr+=[(v,mv)]
    else:
      qr+=[(-1,-1)]
  return ql,qr

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