結果

問題 No.60 魔法少女
ユーザー Navier_Boltzmann
提出日時 2023-12-29 16:51:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 232 ms / 5,000 ms
コード長 1,202 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 124,156 KB
最終ジャッジ日時 2024-09-27 16:16:38
合計ジャッジ時間 3,946 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import *
from itertools import *
from functools import *
from heapq import *
import sys,math
input = sys.stdin.readline

class cs_2d():
    
    def __init__(self,x):
        
            n = len(x)
            m = len(x[0])
            self.n = n
            self.m = m
            
            tmp = [0]*((n+1)*(m+1))
            for i in range(n):
                for j in range(m):
                    tmp[m*(i+1)+j+1] = tmp[m*(i+1)+j] +  tmp[m*i+j+1]  - tmp[m*(i)+j] + x[i][j] 
            
                    
            self.S = tmp
    
    def query(self,ix,jx,iy,jy):
        ##[ix,jx)×[iy,jy)
        
        return self.S[self.m*jx+jy] - self.S[self.m*jx+iy] - self.S[self.m*ix+jy] + self.S[self.m*ix+iy]
N,K = map(int,input().split())
XYH = [tuple(map(int,input().split())) for _ in range(N)]
M = 1501
S = [[0]*(M+1) for _ in range(M+1)]
shift = 500
for _ in range(K):
    a,b,w,h,d = map(int,input().split())

    a += shift
    b += shift
    S[a][b] += d
    S[a+w+1][b] -= d
    S[a][b+h+1] -= d
    S[a+w+1][b+h+1] += d

C = cs_2d(S)

ans = 0
for x,y,h in XYH:
    
    x += shift
    y += shift
    ans += max(0,
               h-C.query(0,x+1,0,y+1))
print(ans)
0