import random #-------- 入力例1 --------- N = 100000 X = [random.randint(1, 1500) for _ inrange(N)] Y = [random.randint(1, 1500) for _ inrange(N)] Q = 100000 A = [random.randint(1, 1500 - 1) for _ inrange(Q)] B = [random.randint(1, 1500 - 1) for _ inrange(Q)] C = [random.randint(A[i] + 1, 1500) for i inrange(Q)] D = [random.randint(B[i] + 1, 1500) for i inrange(Q)] #--------------------------- # 各座標にある点の数をカウント S = [[0] * 1501for i inrange(1501)] for i inrange(N): S[X[i]][Y[i]] += 1
# 2次元累積和を算出 T = [[0] * 1501for i inrange(1501)] for i inrange(1, 1501): for j inrange(1, 1501): T[i][j] = T[i][j - 1] + S[i][j] for j inrange(1, 1501): for i inrange(1, 1501): T[i][j] = T[i - 1][j] + T[i][j]