結果

問題 No.3392 Count 23578 Sequence
コンテスト
ユーザー sasa8uyauya
提出日時 2025-11-28 23:04:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 852 bytes
コンパイル時間 283 ms
コンパイル使用メモリ 82,588 KB
実行使用メモリ 312,048 KB
最終ジャッジ日時 2025-11-28 23:05:14
合計ジャッジ時間 7,379 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

M=2**61-1
B=1235813213455
P=[1,B]
R=[1,pow(B,M-2,M)]
for i in range(2,n+1):
  P+=[P[-1]*P[1]%M]
  R+=[R[-1]*R[1]%M]

X=10**10
b=[X+a[i+1]-a[i] for i in range(n-1)]
hl=b+[0]
for i in range(n-1):
  hl[i]=(hl[i]*P[i]+hl[i-1])%M
hr=b+[0]
for i in reversed(range(n-1)):
  hr[i]=(hr[i]*P[n-2-i]+hr[i+1])%M

ans=0
for i in range(n-1):
  ok=1
  ng=min(i+1,n-1-i)+1
  while ng-ok>1:
    m=(ok+ng)//2
    l=i-m+1
    r=i+m-1
    if 0<=l<=r<n-1 and (hl[r]-hl[l-1])*R[l]%M==(hr[l]-hr[r+1])*R[n-2-r]%M:
      ok=m
    else:
      ng=m
  ans+=ok
for i in range(n-2):
  if b[i]!=b[i+1]:
    continue
  ok=1
  ng=min(i+1,n-2-i)+1
  while ng-ok>1:
    m=(ok+ng)//2
    l=i-m+1
    r=i+1+m-1
    if 0<=l<=r<n-1 and (hl[r]-hl[l-1])*R[l]%M==(hr[l]-hr[r+1])*R[n-2-r]%M:
      ok=m
    else:
      ng=m
  ans+=ok
print(ans+n)
0