結果

問題 No.3464 Max and Sum on Grid
コンテスト
ユーザー titia
提出日時 2026-06-25 03:18:12
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 4,936 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 190 ms
コンパイル使用メモリ 85,248 KB
実行使用メモリ 154,208 KB
最終ジャッジ日時 2026-06-25 03:18:35
合計ジャッジ時間 7,205 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

from operator import itemgetter

N,Q=list(map(int,input().split()))
A=list(map(int,input().split()))
B=list(map(int,input().split()))

Queries=[list(map(int,input().split())) for i in range(Q)]

# class化
class Bit_indexed_tree():
    def __init__(self, LEN):
        self.BIT = [0]*(LEN+1) # 1-indexedなtree. 配列BITの長さはLEN+1にしていることに注意。
        self.LEN = LEN

    def update(self,v,w): # index vにwを加える
        while v<=self.LEN:
            self.BIT[v]+=w
            v+=(v&(-v)) # v&(-v)で、最も下の立っているビット. 自分を含む大きなノードへ. たとえばv=3→v=4

    def getvalue(self,v): # [1,v]の区間の和を求める
        ANS=0
        while v!=0:
            ANS+=self.BIT[v]
            v-=(v&(-v)) # 自分より小さい自分の和を構成するノードへ. たとえばv=14→v=12へ
        return ANS

    def bisect_on_BIT(self,x): # [1,ind]の和がはじめてx以上になるindexを探す

        if x<=0:
            return 0
        
        ANS=0
        h=1<<((self.LEN).bit_length()-1) # LEN以下の最小の2ベキ
        while h>0:
            if ANS+h<=self.LEN and self.BIT[ANS+h]<x:
                x-=self.BIT[ANS+h]
                ANS+=h
            h//=2

        return ANS+1 # LENまでの和がx未満のとき, LEN+1を返すことに注意


LIST=[]

for l,d,r,u in Queries:
    l-=1
    r-=1
    d-=1
    u-=1

    LIST.append((r,u))
    if d-1>=0:
        LIST.append((r,d-1))

    if l-1>=0:
        LIST.append((l-1,u))

    if l-1>=0 and d-1>=0:
        LIST.append((l-1,d-1))

LANS=dict()
LEN=10**5+1

ASUM=Bit_indexed_tree(LEN+1)
AKO=Bit_indexed_tree(LEN+1)

BSUM=Bit_indexed_tree(LEN+1)
BKO=Bit_indexed_tree(LEN+1)

SQ=500

QS=[[] for i in range(N//SQ+2)]

for x,y in LIST:
    QS[x//SQ].append((x,y))

for i in range(len(QS)):
    if i%2==0:
        QS[i].sort(key=itemgetter(1))
    else:
        QS[i].sort(key=itemgetter(1),reverse=True)

nowx=0
nowy=0
ANS=max(A[0],B[0])

ASUM.update(A[0],A[0])
AKO.update(A[0],1)

BSUM.update(B[0],B[0])
BKO.update(B[0],1)

for i in range(len(QS)):
    if i%2==0:
        for x,y in QS[i]:
            while nowx<x:
                a=A[nowx+1]

                plus=BSUM.getvalue(LEN)-BSUM.getvalue(a)
                ko=BKO.getvalue(a)

                ANS+=a*ko+plus

                ASUM.update(A[nowx+1],A[nowx+1])
                AKO.update(A[nowx+1],1)

                nowx+=1

            while nowx>x:
                a=A[nowx]

                plus=BSUM.getvalue(LEN)-BSUM.getvalue(a)
                ko=BKO.getvalue(a)

                ANS-=a*ko+plus

                ASUM.update(A[nowx],-A[nowx])
                AKO.update(A[nowx],-1)

                nowx-=1

            while nowy<y:
                b=B[nowy+1]

                plus=ASUM.getvalue(LEN)-ASUM.getvalue(b)
                ko=AKO.getvalue(b)

                ANS+=b*ko+plus

                BSUM.update(B[nowy+1],B[nowy+1])
                BKO.update(B[nowy+1],1)

                nowy+=1

            while nowx>x:
                b=B[nowy]

                plus=ASUM.getvalue(LEN)-ASUM.getvalue(b)
                ko=AKO.getvalue(b)

                ANS-=b*ko+plus

                BSUM.update(B[nowy],-B[nowy])
                BKO.update(B[nowy],1)

                nowy-=1

            LANS[x,y]=ANS
             
    else:
        for x,y in QS[i]:
            while nowx>x:
                a=A[nowx]

                plus=BSUM.getvalue(LEN)-BSUM.getvalue(a)
                ko=BKO.getvalue(a)

                ANS-=a*ko+plus

                ASUM.update(A[nowx],-A[nowx])
                AKO.update(A[nowx],-1)

                nowx-=1
                
            while nowx<x:
                a=A[nowx+1]

                plus=BSUM.getvalue(LEN)-BSUM.getvalue(a)
                ko=BKO.getvalue(a)

                ANS+=a*ko+plus

                ASUM.update(A[nowx+1],A[nowx+1])
                AKO.update(A[nowx+1],1)

                nowx+=1
            while nowx>x:
                b=B[nowy]

                plus=ASUM.getvalue(LEN)-ASUM.getvalue(b)
                ko=AKO.getvalue(b)

                ANS-=b*ko+plus

                BSUM.update(B[nowy],-B[nowy])
                BKO.update(B[nowy],1)

                nowy-=1

            while nowy<y:
                b=B[nowy+1]

                plus=ASUM.getvalue(LEN)-ASUM.getvalue(b)
                ko=AKO.getvalue(b)

                ANS+=b*ko+plus

                BSUM.update(B[nowy+1],B[nowy+1])
                BKO.update(B[nowy+1],1)

                nowy+=1

            LANS[x,y]=ANS


#print(*LANS)

for l,d,r,u in Queries:
    l-=1
    r-=1
    d-=1
    u-=1
    
    score=0

    score+=LANS[(r,u)]
    if d-1>=0:
        score-=LANS[(r,d-1)]

    if l-1>=0:
        score-=LANS[(l-1,u)]

    if l-1>=0 and d-1>=0:
        score+=LANS[(l-1,d-1)]

    print(score)
0