結果

問題 No.60 魔法少女
ユーザー Navier_BoltzmannNavier_Boltzmann
提出日時 2023-12-29 16:51:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 273 ms / 5,000 ms
コード長 1,202 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 123,320 KB
最終ジャッジ日時 2023-12-29 16:51:38
合計ジャッジ時間 4,380 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
106,140 KB
testcase_01 AC 99 ms
106,132 KB
testcase_02 AC 94 ms
106,136 KB
testcase_03 AC 96 ms
106,124 KB
testcase_04 AC 210 ms
114,068 KB
testcase_05 AC 208 ms
123,040 KB
testcase_06 AC 249 ms
122,628 KB
testcase_07 AC 213 ms
119,920 KB
testcase_08 AC 185 ms
118,380 KB
testcase_09 AC 148 ms
114,460 KB
testcase_10 AC 273 ms
123,100 KB
testcase_11 AC 121 ms
104,880 KB
testcase_12 AC 177 ms
119,908 KB
testcase_13 AC 250 ms
123,320 KB
権限があれば一括ダウンロードができます

ソースコード

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