結果

問題 No.60 魔法少女
ユーザー Navier_BoltzmannNavier_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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 87 ms
106,528 KB
testcase_01 AC 90 ms
106,596 KB
testcase_02 AC 87 ms
106,628 KB
testcase_03 AC 87 ms
106,700 KB
testcase_04 AC 160 ms
114,332 KB
testcase_05 AC 175 ms
124,096 KB
testcase_06 AC 210 ms
123,448 KB
testcase_07 AC 184 ms
120,424 KB
testcase_08 AC 161 ms
118,804 KB
testcase_09 AC 131 ms
114,856 KB
testcase_10 AC 211 ms
123,608 KB
testcase_11 AC 109 ms
105,148 KB
testcase_12 AC 157 ms
120,312 KB
testcase_13 AC 232 ms
124,156 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