結果

問題 No.1965 Heavier
コンテスト
ユーザー ああ
提出日時 2026-05-12 22:53:05
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,019 ms / 2,000 ms
コード長 1,376 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 269 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 370,580 KB
最終ジャッジ日時 2026-05-12 22:53:23
合計ジャッジ時間 17,345 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

def aa(m,seg):
    while m>1:
        m//=2
        seg[m]=max(seg[m*2],seg[m*2+1])
def bb(l,r,seg):
    res=-1<<60
    while l<r:
        if l&1:
            res=max(res,seg[l]);l+=1
        if r&1:
            r-=1;res=max(res,seg[r])
        l//=2;r//=2
    return res

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
s=set(b)
v=1<<len(s).bit_length()
y={};p=0
for i in sorted(list(s)):
    y[i]=p+v;p+=1
c=[deque() for i in range(len(s))]
d=[deque() for i in range(len(s))]
seg1=[0]*v*2;ans=0
seg2=[-1<<60]*v*2;q=0
for i in range(n):
    while q<n:
        j,l=a[q],b[q]
        if bb(v,y[l],seg2)>=j-l or bb(y[l],v*2,seg1)>=l+j:
            break
        q+=1
        k=y[l]-v
        while c[k] and c[k][-1]<j-l:
            c[k].popleft()
        c[k].append(j-l)
        seg2[k+v]=c[k][0];aa(k+v,seg2)
        while d[k] and d[k][-1]<l+j:
            d[k].popleft()
        d[k].append(l+j)
        seg1[k+v]=d[k][0];aa(k+v,seg1)
    ans+=q-i-1
    k=y[b[i]]-v
    j,l=a[i],b[i]
    if c[k][0]==j-l:
        c[k].popleft()
        if c[k]:
            seg2[k+v]=c[k][0];aa(k+v,seg2)
        else:
            seg2[k+v]=-1<<60;aa(k+v,seg2)
    if d[k][0]==j+l:
        d[k].popleft()
        if d[k]:
            seg1[k+v]=d[k][0];aa(k+v,seg1)
        else:
            seg1[k+v]=0;aa(k+v,seg1)
print(ans)
0