Problem:


天体観測

ある晴れた夜の帰り道、空を見上げるとそこには無数の星。強く輝く星々、かすかに見える星々、いろ
いろな明るさの星々が夜空を彩っています。

あなたはふと思いました。この星空に自分の星座があったらどんなに素敵だろうと。そこであなたはひとつの基準を決め、部屋の窓から見える星々を適当につなげて自分の星座を作ることにしました。その基準とは、「どの２つの星を選んでも、それらの明るさの差がある定数 d 以下になるような星のグループを作り、その中で一番大きいものを自分の星座にしよう！」というものです。例えば、図のような窓から見える夜空を考えてみましょう（外側の長方形は窓枠です）。 

この夜空には、明るさがそれぞれ 1，12, 2，4，1，8, 3，5，4 の９つの星がありますが、d = 2 とすると例えば以下のような３つの星座 A, B, C ができます。

大きさが 12 の星座 A
大きさが 10 の星座 B
大きさが 16 の星座 C

星座の大きさを次のように決めることにしました。ある星座の星をすべて含むような、窓枠に平行な辺からなる長方形のうち、面積が最も小さいものを選びます。この長方形の面積をその星座の大きさとします。例えば、上の夜空では星座 A, B, Cの大きさはそれぞれ12, 10, 16になるので、星座Cが最も大きい星座となります。

N 個の星の位置と明るさ、および整数 d が与えられたとき、一番大きい星座の面積を求めるプログラムを作成してください。星の位置は窓枠の左下隅を原点とした座標で与えられ、軸は図のような向きとします。星座を構成する星が１つの場合や、星々が軸に平行な直線上にある場合は、その星座の面積は 0 となることに注意してください。

入力

入力は以下の形式で与えられる。 

N d
x1 y1 b1
x2 y2 b2
:
xN yN bN

1 行目に星の数 N (1 ≤ N ≤ 200000) と整数 d (0 ≤ d ≤ 109) が与えられる。続く N 行に、i 番目の星の座標を表す整数 xi (0 ≤ xi ≤ 2000000) と yi (0 ≤ yi ≤ 2000000)、明るさを表す整数 bi (0 ≤ bi ≤ 109) が与えられる。入力される星の座標はすべて異なる。

出力

一番大きい星座の面積を１行に出力する。

入出力例

入力例

9 2
1 1 1
1 5 12
2 3 2
3 2 4
4 4 1
5 1 3
5 3 8
6 5 5
7 2 4

 出力例

16 



Sample input:
9 2
1 1 1
1 5 12
2 3 2
3 2 4
4 4 1
5 1 3
5 3 8
6 5 5
7 2 4


Sample output:
16

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log2


class SegmentTree:
    def __init__(self, n, bounds):
        n2 = 2 ** ceil(log2(n))
        tree = [None] * (n2 - 1) + bounds + [None] * (n2 - n)
        left = [0] * (n2 - 1) + list(range(n2))
        right = [0] * (n2 - 1) + list(range(n2))
        for i in range(n2 - 2, -1, -1):
            tree[i] = bound_expand(tree[i * 2 + 1], tree[i * 2 + 2])
            left[i] = left[i * 2 + 1]
            right[i] = right[i * 2 + 2]
        self.tree = tree
        self.left = left
        self.right = right

    def get(self, s, t, i=0):
        l, r = self.left[i], self.right[i]
        if l >= s and r <= t:
            return self.tree[i]
        if l > t or r < s:
            return None
        return bound_expand(self.get(s, t, i * 2 + 1), self.get(s, t, i * 2 + 2))


def bound_expand(b1, b2):
    if b1:
        if b2:
            return tuple(f(xy1, xy2) for f, xy1, xy2 in zip((min, min, max, max), b1, b2))
        return b1
    return b2


def bound_area(b):
    return (b[2] - b[0]) * (b[3] - b[1])


n, d = map(int, input().split())
input_store = set()
max_b = -1

while n:
    x, y, b = map(int, input().split())
    input_store.add((x, y, b))
    if b > max_b: max_b = b
    n -= 1

stars = [None] * (max_b + 1)
for x, y, b in input_store:
    stars[b] = bound_expand(stars[b], (x, y, x, y))

st = SegmentTree(max_b + 1, stars)

print(max(bound_area(st.get(i, i + d)) for i, b in enumerate(stars) if b))

Submission status: Time Limit Exceeded

Solution code:
answer=[]
info = list(map(int,raw_input().split()))
all_list=[] # This list include information of all stars.
for i in range (info[0]):
	all_list.append(list(map(int,raw_input().split())))
dark_star=min(all_list, key=lambda x: x[2])[2]
bright_star=max(all_list, key=lambda x:x[2])[2]

for i in range (dark_star,bright_star+1):
	li_xyd=[]
	li_x=[]
	li_y=[]
	for j in range (i,i+info[1]+1):
		add_list=list(filter(lambda x:x[2]==j,all_list))
		if add_list != []:
			li_xyd+=add_list[:]
		else:
			pass
	for j in li_xyd:
		li_x.append(j[0])
		li_y.append(j[1])
	if li_x==[]:
		li_x=[0]
	if li_y==[]:
		li_y=[0]
	num = (max(li_x)-min(li_x))*(max(li_y)-min(li_y))
	answer.append(num)
print(max(answer))

Submission status: Time Limit Exceeded

Solution code:
answer=[]
info = list(map(int,raw_input().split()))
all_list=[] # This list include information of all stars.
for i in range (info[0]):
	all_list.append(list(map(int,raw_input().split())))
dark_star=min(all_list, key=lambda x: x[2])[2]
bright_star=max(all_list, key=lambda x:x[2])[2]
for i in range (dark_star,bright_star+1):
	li=filter(lambda x: i<=x[2]<=i+info[1],all_list)
	if li !=[]:
		answer.append((max(li,key=lambda x:x[0])[0]-min(li,key=lambda x:x[0])[0])*(max(li,key=lambda x:x[1])[1]-min(li,key=lambda x:x[1])[1]))
print max(answer)

Submission status: Time Limit Exceeded

Solution code:
N,d = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
L = sorted(L,key=lambda x:x[2])

def get_square(L):
  if not L:return 0
  x=[L[0][0],L[0][0]]
  y=[L[0][1],L[0][1]]
  for i in L:
    if i[0] < x[0]:x[0] = i[0]
    if i[0] > x[1]:x[1] = i[0]
    if i[1] < y[0]:y[0] = i[1]
    if i[1] > y[1]:y[1] = i[1]
  return (x[1] - x[0]) * (y[1] - y[0])

result = 0
i = L[0][2]
j = L[-1][2]
while True:
  n = i + d
  l = []
  while i <= n:
    l += [x for x in L if x[2] == i]
    i += 1
  s = get_square(l)
  if result < s:result = s
  i -= d
  if j < i + d:break
print(result)

Submission status: Time Limit Exceeded

Solution code:
N,d = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
L = sorted(L,key=lambda x:x[2])

def get_square(L):
  if not L or len(L) == 0:return 0
  x=[L[0][0],L[0][0]]
  y=[L[0][1],L[0][1]]
  for i in L:
    if i[0] < x[0]:x[0] = i[0]
    if i[0] > x[1]:x[1] = i[0]
    if i[1] < y[0]:y[0] = i[1]
    if i[1] > y[1]:y[1] = i[1]
  return (x[1] - x[0]) * (y[1] - y[0])

result = 0
i = L[0][2]
j = L[-1][2]
while True:
  n = i + d
  l = []
  while i <= n:
    l += [x[0:2] for x in L if x[2] == i]
    i += 1
  s = get_square(l)
  if result < s:result = s
  i -= d
  if j < i + d:break
print(result)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
N,d = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
L = sorted(L,key=itemgetter(2,0,1))

def get_square(L):
  if not L or len(L) == 0:return 0
  x=[L[0][0],L[0][0]]
  y=[L[0][1],L[0][1]]
  for i in L:
    if i[0] < x[0]:x[0] = i[0]
    elif i[0] > x[1]:x[1] = i[0]
    if i[1] < y[0]:y[0] = i[1]
    elif i[1] > y[1]:y[1] = i[1]
  return (x[1] - x[0]) * (y[1] - y[0])

result = 0
i = L[0][2]
j = L[-1][2]
while True:
  n = i + d
  l = []
  while i <= n:
    l += [x[0:2] for x in L if x[2] == i]
    i += 1
  s = get_square(l)
  if result < s:result = s
  i -= d
  if j < i + d:break
print(result)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
N,d = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
L = sorted(L,key=itemgetter(2,0,1))

def get_square(L):
  if not L or len(L) == 0:return 0
  x=[L[0][0][0],L[0][0][1]]
  y=[L[0][1][0],L[0][1][1]]
  for i in L:
    if i[0][0] < x[0]:x[0] = i[0][0]
    if i[0][1] > x[1]:x[1] = i[0][1]
    if i[1][0] < y[0]:y[0] = i[1][0]
    if i[1][1] > y[1]:y[1] = i[1][1]
  return (x[1] - x[0]) * (y[1] - y[0])

def get_xy(b,L):
  if not L or len(L) == 0:return None
  x=[L[0][0],L[0][0]]
  y=[L[0][1],L[0][1]]
  for i in L:
    if i[0] < x[0]:x[0] = i[0]
    elif i[0] > x[1]:x[1] = i[0]
    if i[1] < y[0]:y[0] = i[1]
    elif i[1] > y[1]:y[1] = i[1]
  return (b,x,y)

D = []
for n in range(0,L[-1][2]+1):
  xy = get_xy(n,[i for i in L if i[2] == n])
  if xy:D.append(xy)

i = 0
result = 0
while i < len(D):
  m = D[i][0] + d
  L = [D[i][1:3]]
  j = i+1
  while j < len(D) and D[j][0] <= m:
    L.append(D[j][1:3])
    j += 1
  s = get_square(L)
  if result < s:result = s
  i += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter
N,d = map(int,input().split())
L = sorted([list(map(int,i.split())) for i in stdin.readlines()],key=itemgetter(2))
#L = [list(map(int,input().split())) for i in range(N)]
#L = sorted(L,key=itemgetter(2,0,1))

def get_square(L):
  if not L or len(L) == 0:return 0
  x=[L[0][0][0],L[0][0][1]]
  y=[L[0][1][0],L[0][1][1]]
  for i in L:
    if i[0][0] < x[0]:x[0] = i[0][0]
    if i[0][1] > x[1]:x[1] = i[0][1]
    if i[1][0] < y[0]:y[0] = i[1][0]
    if i[1][1] > y[1]:y[1] = i[1][1]
  return (x[1] - x[0]) * (y[1] - y[0])

def get_xy(b,L):
  if not L or len(L) == 0:return None
  x=[L[0][0],L[0][0]]
  y=[L[0][1],L[0][1]]
  for i in L:
    if i[0] < x[0]:x[0] = i[0]
    elif i[0] > x[1]:x[1] = i[0]
    if i[1] < y[0]:y[0] = i[1]
    elif i[1] > y[1]:y[1] = i[1]
  return (b,x,y)

D = []
for n in range(0,L[-1][2]+1):
  xy = get_xy(n,[i for i in L if i[2] == n])
  if xy:D.append(xy)

i = 0
result = 0
while i < len(D):
  m = D[i][0] + d
  L = [D[i][1:3]]
  j = i+1
  while j < len(D) and D[j][0] <= m:
    L.append(D[j][1:3])
    j += 1
  s = get_square(L)
  if result < s:result = s
  i += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter

def get_square(L):
  if not L or len(L) == 0:return 0
  x=[L[0][0][0],L[0][0][1]]
  y=[L[0][1][0],L[0][1][1]]
  for i in L:
    if i[0][0] < x[0]:x[0] = i[0][0]
    if i[0][1] > x[1]:x[1] = i[0][1]
    if i[1][0] < y[0]:y[0] = i[1][0]
    if i[1][1] > y[1]:y[1] = i[1][1]
  return (x[1] - x[0]) * (y[1] - y[0])

def get_xy(b,L):
  if not L or len(L) == 0:return None
  x=[L[0][0],L[0][0]]
  y=[L[0][1],L[0][1]]
  for i in L:
    if i[0] < x[0]:x[0] = i[0]
    elif i[0] > x[1]:x[1] = i[0]
    if i[1] < y[0]:y[0] = i[1]
    elif i[1] > y[1]:y[1] = i[1]
  return (b,x,y)

N,d = map(int,input().split())
L = sorted([list(map(int,i.split())) for i in stdin.readlines()],key=itemgetter(2))
B = set([i[2] for i in L])
D = [get_xy(n,[i for i in L if i[2] == n]) for n in B]

i = 0
result = 0
while i < len(D):
  m = D[i][0] + d
  L = [D[i][1:3]]
  j = i+1
  while j < len(D) and D[j][0] <= m:
    L.append(D[j][1:3])
    j += 1
  s = get_square(L)
  if result < s:result = s
  i += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter

def get_square(L):
  if not L or len(L) == 0:return 0
  x=[L[0][0][0],L[0][0][1]]
  y=[L[0][1][0],L[0][1][1]]
  for i in L:
    if i[0][0] < x[0]:x[0] = i[0][0]
    if i[0][1] > x[1]:x[1] = i[0][1]
    if i[1][0] < y[0]:y[0] = i[1][0]
    if i[1][1] > y[1]:y[1] = i[1][1]
  return (x[1] - x[0]) * (y[1] - y[0])

def get_xy(b,L):
  if not L or len(L) == 0:return None
  x=[L[0][0],L[0][0]]
  y=[L[0][1],L[0][1]]
  for i in L:
    if i[0] < x[0]:x[0] = i[0]
    elif i[0] > x[1]:x[1] = i[0]
    if i[1] < y[0]:y[0] = i[1]
    elif i[1] > y[1]:y[1] = i[1]
  return (b,x,y)

N,d = map(int,input().split())
L = sorted(set([tuple(map(int,i.split())) for i in stdin.readlines()]),key=itemgetter(2))
B = set([i[2] for i in L])
D = [get_xy(n,[i for i in L if i[2] == n]) for n in B]

i = 0
result = 0
while i < len(D):
  m = D[i][0] + d
  L = [D[i][1:3]]
  j = i+1
  while j < len(D) and D[j][0] <= m:
    L.append(D[j][1:3])
    j += 1
  s = get_square(L)
  if result < s:result = s
  i += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter

def get_square(L):
  if not L or len(L) == 0:return 0
  x=[L[0][0][0],L[0][0][1]]
  y=[L[0][1][0],L[0][1][1]]
  for i in L:
    if i[0][0] < x[0]:x[0] = i[0][0]
    if i[0][1] > x[1]:x[1] = i[0][1]
    if i[1][0] < y[0]:y[0] = i[1][0]
    if i[1][1] > y[1]:y[1] = i[1][1]
  return (x[1] - x[0]) * (y[1] - y[0])

def get_xy(b,L):
  if not L or len(L) == 0:return None
  x=[L[0][0],L[0][0]]
  y=[L[0][1],L[0][1]]
  for i in L:
    if i[0] < x[0]:x[0] = i[0]
    elif i[0] > x[1]:x[1] = i[0]
    if i[1] < y[0]:y[0] = i[1]
    elif i[1] > y[1]:y[1] = i[1]
  return (b,x,y)

N,d = map(int,input().split())
L = set([tuple(map(int,i.split())) for i in stdin.readlines()])
B = set([i[2] for i in L])
D = [get_xy(n,[i for i in L if i[2] == n]) for n in B]

i = 0
result = 0
while i < len(D):
  m = D[i][0] + d
  L = [D[i][1:3]]
  j = i+1
  while j < len(D) and D[j][0] <= m:
    L.append(D[j][1:3])
    j += 1
  s = get_square(L)
  if result < s:result = s
  i += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter

def get_square(L):
  if not L or len(L) == 0:return 0
  x=[L[0][0][0],L[0][0][1]]
  y=[L[0][1][0],L[0][1][1]]
  for i in L:
    if i[0][0] < x[0]:x[0] = i[0][0]
    if i[0][1] > x[1]:x[1] = i[0][1]
    if i[1][0] < y[0]:y[0] = i[1][0]
    if i[1][1] > y[1]:y[1] = i[1][1]
  return (x[1] - x[0]) * (y[1] - y[0])

def get_xy(b,L):
  if not L or len(L) == 0:return None
  x = (min(L[0]),max(L[0]))
  y = (min(L[1]),max(L[1]))
#  x=[L[0][0],L[0][0]]
#  y=[L[0][1],L[0][1]]
#  for i in L:
#    if i[0] < x[0]:x[0] = i[0]
#    elif i[0] > x[1]:x[1] = i[0]
#    if i[1] < y[0]:y[0] = i[1]
#    elif i[1] > y[1]:y[1] = i[1]
  return (b,x,y)

N,d = map(int,input().split())
L = set([tuple(map(int,i.split())) for i in stdin.readlines()])
B = set([i[2] for i in L])

D = [get_xy(n,list(zip(*[i[0:2] for i in L if i[2] == n]))) for n in B]

i = 0
result = 0
while i < len(D):
  m = D[i][0] + d
  L = [D[i][1:3]]
  j = i+1
  while j < len(D) and D[j][0] <= m:
    L.append(D[j][1:3])
    j += 1
  s = get_square(L)
  if result < s:result = s
  i += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter
from itertools import takewhile
from random import randint

def make_data(n):
  return [str(randint(0,2000000))+' '+str(randint(0,2000000))+' '+str(randint(0,1e9))
      for i in range(n)]

def get_square(x_min,x_max,y_min,y_max):
  return (x_max - x_min) * (y_max - y_min)

N,d = map(int,input().split())
L = [tuple(map(int,i.split())) for i in stdin.readlines()]
#L = [tuple(map(int,i.split())) for i in make_data(N)]
B = sorted(set([i[2] for i in L]))
D = {i:[] for i in B}
[D[i[2]].append((i[0],i[1])) for i in L]
for k,v in D.items():
  i = tuple(zip(*v))
  D[k] = (min(i[0]),max(i[0]),min(i[1]),max(i[1]))

Max = B[-1]
result = 0

i = 0
while i < len(B):
  b = B[i] + d
  L2 = [D[j] for j in 
      takewhile(
        lambda x: x <= b, 
        (B[n] for n in range(i,len(B)))
        ) ]
  L3 = tuple(zip(*L2))
  s = get_square(min(L3[0]),max(L3[1]),min(L3[2]),max(L3[3]))
  if result < s:result = s
  if B[i]+d > Max:break
  i += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter
from itertools import takewhile
from random import randint

def make_data(n):
  return [str(randint(0,2000000))+' '+str(randint(0,2000000))+' '+str(randint(0,1e9))
      for i in range(n)]

def get_square(x_min,x_max,y_min,y_max):
  return (x_max - x_min) * (y_max - y_min)

N,d = map(int,input().split())
L = [tuple(map(int,i.split())) for i in stdin.readlines()]
#L = [tuple(map(int,i.split())) for i in make_data(N)]
B = sorted(set([i[2] for i in L]))
D = {i:[] for i in B}
[D[i[2]].append((i[0],i[1])) for i in L]
for k,v in D.items():
  i = tuple(zip(*v))
  D[k] = (min(i[0]),max(i[0]),min(i[1]),max(i[1]))

Max = B[-1]
result = 0

i = 0
while i < len(B):
  b = B[i] + d
  L2 = (D[j] for j in 
      takewhile(
        lambda x: x <= b, 
        (B[n] for n in range(i,len(B)))
        ))
  L3 = tuple(zip(*L2))
  s = get_square(min(L3[0]),max(L3[1]),min(L3[2]),max(L3[3]))
  if result < s:result = s
  if B[i]+d > Max:break
  i += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter as it
D={}
result=[]
N,d=map(int,input().split())
for i in stdin.readlines():
    x,y,b=map(int,i.split())
    if b not in D:D[b]=[]
    D[b].append((x,y))
for i in range(max(D)-d+1):
    l=[]
    for s in range(d+1):
        if i+s in D:l+=D[i+s]
    if len(l)>1:
        x=max(map(it(0),l))-min(map(it(0),l))
        y=max(map(it(1),l))-min(map(it(1),l))
        result.append(x*y)
print(0 if 0==len(result) else max(result))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter as it
D={}
result=[]
N,d=map(int,input().split())
for i in stdin.readlines():
    x,y,b=map(int,i.split())
    if b not in D:D[b]=[]
    D[b].append((x,y))
for i in range(max(D)-d+1):
    l=[]
    for s in range(d+1):
        if i+s in D:l+=D[i+s]
    if len(l)>1:
        if len(l)>1:result.append((max(map(it(0),l))-min(map(it(0),l)))*(max(map(it(1),l))-min(map(it(1),l))))
print(0 if 0==len(result) else max(result))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter as it
D={}
result=[]
N,d=map(int,input().split())
for i in stdin.readlines():
    x,y,b=map(int,i.split())
    if b not in D:D[b]=[]
    D[b].append((x,y))
for i in range(max(D)-d+1):
    l=[]
    for s in range(d+1):
        if i+s in D:l+=D[i+s]
    if len(l)>1:
        if len(l)>1:
            x,y=it(0),it(1)
            result.append((max(map(x,l))-min(map(x,l)))*(max(map(y,l))-min(map(y,l))))
print(0 if 0==len(result) else max(result))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter
from itertools import takewhile
from random import randint
from array import array

def make_data(n):
  return [str(randint(0,2000000))+' '+str(randint(0,2000000))+' '+str(randint(0,1e9))
      for i in range(n)]

def get_square(x_min,x_max,y_min,y_max):
  return (x_max - x_min) * (y_max - y_min)

N,d = map(int,input().split())
L = [tuple(map(int,i.split())) for i in stdin.readlines()]
#L = [tuple(map(int,i.split())) for i in make_data(N)]
B = sorted(set([i[2] for i in L]))
D = {i:[] for i in B}
[D[i[2]].append((i[0],i[1])) for i in L]
for k,v in D.items():
  i = tuple(zip(*v))
  D[k] = array('L',(min(i[0]),max(i[0]),min(i[1]),max(i[1])))
Max = B[-1]
result = 0

for i in range(len(B)):
  b = B[i] + d
  L2 = (D[j] for j in 
      takewhile(
        lambda x: x <= b, 
        (B[n] for n in range(i,len(B)))
        ))
  L3 = tuple(zip(*L2))
  s = get_square(min(L3[0]),max(L3[1]),min(L3[2]),max(L3[3]))
  #s = (max(L3[1]) - min(L3[0])) * (max(L3[3]) - min(L3[2]))
  if result < s:result = s
  if b > Max:break
print(result)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from operator import itemgetter
from itertools import takewhile
from random import randint
from array import array

MAX = 200000000

class Point:
  def __init__(self,x=-1,y=-1,b=-1):
    self.x=x
    self.y=y
    self.b=b

class Points:
  def __init__(self,b,points):
    self.b=b
    self.xmin=points[0]
    self.xmax=points[1]
    self.ymin=points[2]
    self.ymax=points[3]

  def set_point(self,point):
    if self.xmin > point.x:self.xmin=point.x
    elif self.xmax < point.x:self.xmax=point.x
    if self.ymin > point.y:self.ymin=point.y
    elif self.ymax < point.y:self.ymax=point.y

class Constellation:
  def __init__(self,bmin=0,bmax=0,xmin=0,xmax=0,ymin=0,ymax=0):
    self.D = { i:None for i in range(bmin,bmax+1) }
    self.bmin=bmin
    self.bmax=bmax
    self.xmin=xmin
    self.xmax=xmax
    self.ymin=ymin
    self.ymax=ymax

  def set_points(self,points):
    if points.b > self.bmax and points.b < self.bmin:
      raise Exception
    if self.xmin > points.xmin:self.xmin=points.xmin
    elif self.xmax < points.xmax:self.xmax=points.xmax
    if self.ymin > points.ymin:self.ymin=points.ymin
    elif self.ymax < points.ymax:self.ymax=points.ymax

  def square(self):
    return (self.xmax - self.xmin) * (self.ymax - self.ymin)

  def update_b(self,bmin=0,bmax=0):
    for i in range(self.bmin,bmin):
      del self.D[i]
    for i in range(self.bmax+1,bmax+1):
      self.D[i] = None
    self.bmin = bmin
    self.bmax = bmax


N,d = map(int,input().split())
L = [tuple(map(int,i.split())) for i in stdin.readlines()]
B = sorted(set([i[2] for i in L]))
D = {i:[] for i in B}
[D[i[2]].append((i[0],i[1])) for i in L]
for k,v in D.items():
  i = tuple(zip(*v))
  D[k] = (min(i[0]),max(i[0]),min(i[1]),max(i[1]))
Max = B[-1]
result = 0

if d < 50000:
  for i in range(len(B)):
    b = B[i] + d
    L2 = tuple(zip(*(D[j] for j in 
        takewhile(
          lambda x: x <= b, 
          (B[n] for n in range(i,len(B)))
          ))))
    s = (max(L2[1]) - min(L2[0])) * (max(L2[3]) - min(L2[2]))
    if result < s:result = s
    if b > Max:break
  print(result)

else:
  results = 0
  print(B[0])
  print(B[0]+d)
  print(D[B[0]])
  c = Constellation(B[0],B[0]+d,*D[B[0]])
  for k,v in D.items(): # k b, v xminmax,yminmax
    if k <= c.bmax:
      c.set_points(Points(k,v))
      continue
    s = c.square()
    if result < s:result = s
    c.update_b(k-d,k)
    c.set_points(Points(k,v))

  print(result)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br
class Node:
  def __init__(self, val, sec):
    self.val = val
    self.sec = sec
    self.left = sec[0]
    self.right = sec[1]
    self.minx = val[0]
    self.maxx = val[1]
    self.miny = val[2]
    self.maxy = val[3]

class SegTree:
  def __init__(self, num, lst):
    num_ = 1
    while num_ < num:
      num_ *= 2
    self.length = num_ * 2 - 1
    self.arr = [None] * (num_ * 2 - 1)
    for i in range(num):
      self.arr[num_ - 1 + i] = Node(lst[i], (i, i))

    self.make(0)

  def make(self, num):
    if num >= self.length:
      return None
    if self.arr[num] != None:
      return self.arr[num]
    else:
      self.arr[num] = self.con(self.make(num * 2 + 1), self.make(num * 2 + 2))
      return self.arr[num]
  
  def con(self, n1, n2):
    if n1 != None and n2 != None:
      return Node((min(n1.minx, n2.minx), max(n1.maxx, n2.maxx), min(n1.miny, n2.miny), max(n1.maxy, n2.maxy)),
                  (n1.left, n2.right))
    if n1 != None:
      return n1
    if n2 != None:
      return n2
    return None

  def query(self, l, r, num):
    node = self.arr[num]
    if node == None:
      return None
    if l <= node.left and node.right <= r:
      return node
    elif r < node.left or node.right < l:
      return None
    else:
      return self.con(self.query(l, r, num * 2 + 1), self.query(l, r, num * 2 + 2))

def main():
  n, d = map(int, input().split())
  stars = []
  blst = []
  for _ in range(n):
    x, y, b = map(int, input().split())
    stars.append((x, y, b))
    blst.append(b)
  blst.sort()
  stars.sort(key=lambda t:t[2])
  stars = [(x, x, y, y) for x, y, _ in stars]

  tree = SegTree(n, stars)
  ans = 0
  for l in range(n):
    r = br(blst, blst[l] + d)
    if r == n:
      r -= 1
    elif blst[r] != blst[l] + d:
      r -= 1
    a = tree.query(l, r, 0).val
    ans = max((a[1] - a[0]) * (a[3] - a[2]), ans)
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br

class Node:
  def __init__(self, val, sec):
    self.val = val
    self.sec = sec
    self.left = sec[0]
    self.right = sec[1]
    self.minx = val[0]
    self.maxx = val[1]
    self.miny = val[2]
    self.maxy = val[3]

class SegTree:
  def __init__(self, num, lst):
    num_ = 1
    while num_ < num:
      num_ *= 2
    self.length = num_ * 2 - 1
    self.arr = [None] * (num_ * 2 - 1)
    for i in range(num):
      self.arr[num_ - 1 + i] = Node(lst[i], (i, i))

    self.make(0)

  def make(self, num):
    if num >= self.length:
      return None
    if self.arr[num] != None:
      return self.arr[num]
    else:
      self.arr[num] = self.con(self.make(num * 2 + 1), self.make(num * 2 + 2))
      return self.arr[num]
  
  def con(self, n1, n2):
    if n1 != None and n2 != None:
      return Node((min(n1.minx, n2.minx), max(n1.maxx, n2.maxx), min(n1.miny, n2.miny), max(n1.maxy, n2.maxy)),
                  (n1.left, n2.right))
    if n1 != None:
      return n1
    if n2 != None:
      return n2
    return None

  def query(self, l, r, num):
    node = self.arr[num]
    if node == None:
      return None
    if l <= node.left and node.right <= r:
      return node.val
    elif r < node.left or node.right < l:
      return None
    else:
      x1 = self.query(l, r, num * 2 + 1)
      x2 = self.query(l, r, num * 2 + 2)
      if x1 == None and x2 == None:
        return None
      if x1 == None:
        return x2
      if x2 == None:
        return x1
      return (min(x1[0], x2[0]), max(x1[1], x2[1]), min(x1[2], x2[2]), max(x1[3], x2[3]))

def main():
  n, d = map(int, input().split())
  stars = []
  blst = []
  for _ in range(n):
    x, y, b = map(int, input().split())
    stars.append((x, y, b))
    blst.append(b)
  blst.sort()
  stars.sort(key=lambda t:t[2])
  stars = [(x, x, y, y) for x, y, _ in stars]

  tree = SegTree(n, stars)
  ans = 0
  for l in range(n):
    r = br(blst, blst[l] + d)
    if r == n:
      r -= 1
    elif blst[r] != blst[l] + d:
      r -= 1
    a = tree.query(l, r, 0)
    ans = max((a[1] - a[0]) * (a[3] - a[2]), ans)
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br

class Node:
  def __init__(self, val, sec):
    self.val = val
    self.sec = sec
    self.left = sec[0]
    self.right = sec[1]
    self.minx = val[0]
    self.maxx = val[1]
    self.miny = val[2]
    self.maxy = val[3]

class SegTree:
  def __init__(self, num, lst):
    num_ = 1
    while num_ < num:
      num_ *= 2
    self.length = num_ * 2 - 1
    self.arr = [None] * (num_ * 2 - 1)
    for i in range(num):
      self.arr[num_ - 1 + i] = Node(lst[i], (i, i))

    self.make(0)

  def make(self, num):
    if num >= self.length:
      return None
    if self.arr[num] != None:
      return self.arr[num]
    else:
      self.arr[num] = self.con(self.make(num * 2 + 1), self.make(num * 2 + 2))
      return self.arr[num]
  
  def con(self, n1, n2):
    if n1 != None and n2 != None:
      return Node((min(n1.minx, n2.minx), max(n1.maxx, n2.maxx), min(n1.miny, n2.miny), max(n1.maxy, n2.maxy)),
                  (n1.left, n2.right))
    if n1 != None:
      return n1
    if n2 != None:
      return n2
    return None

  def query(self, l, r, num):
    node = self.arr[num]
    if node == None:
      return None
    if l <= node.left and node.right <= r:
      return node.val
    elif r < node.left or node.right < l:
      return None
    else:
      x1 = self.query(l, r, num * 2 + 1)
      x2 = self.query(l, r, num * 2 + 2)
      if x1 == None and x2 == None:
        return None
      if x1 == None:
        return x2
      if x2 == None:
        return x1
      return (min(x1[0], x2[0]), max(x1[1], x2[1]), min(x1[2], x2[2]), max(x1[3], x2[3]))

def main():
  n, d = map(int, input().split())
  stars = []
  blst = []
  for _ in range(n):
    x, y, b = map(int, input().split())
    stars.append((x, y, b))
    blst.append(b)
  blst.sort()
  stars.sort(key=lambda t:t[2])
  stars = [(x, x, y, y) for x, y, _ in stars]

  tree = SegTree(n, stars)
  ans = 0
  max_r = 0
  for l in range(n):
    r = br(blst, blst[l] + d)
    if r == n:
      r -= 1
    elif blst[r] != blst[l] + d:
      r -= 1
    if r > max_r:
      a = tree.query(l, r, 0)
      ans = max((a[1] - a[0]) * (a[3] - a[2]), ans)
      max_r = r
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br

class SegTree:
  def __init__(self, num, lst):
    num_ = 1
    while num_ < num:
      num_ *= 2
    self.length = num_ * 2 - 1
    self.arr = [None] * (num_ * 2 - 1)
    for i in range(num):
      x1, x2, y1, y2 = lst[i]
      self.arr[num_ - 1 + i] = (x1, x2, y1, y2, i, i)

    self.make(0)

  def make(self, num):
    if num >= self.length:
      return None
    if self.arr[num] != None:
      return self.arr[num]
    else:
      self.arr[num] = self.con(self.make(num * 2 + 1), self.make(num * 2 + 2))
      return self.arr[num]
  
  def con(self, n1, n2):
    if n1 != None and n2 != None:
      return ((min(n1[0], n2[0]), max(n1[1], n2[1]), min(n1[2], n2[2]), max(n1[3], n2[3]), n1[4], n2[5]))
    if n1 != None:
      return n1
    if n2 != None:
      return n2
    return None

  def query(self, l, r, num):
    node = self.arr[num]
    if node == None:
      return None
    if l <= node[4] and node[5] <= r:
      return node[:4]
    elif r < node[4] or node[5] < l:
      return None
    else:
      x1 = self.query(l, r, num * 2 + 1)
      x2 = self.query(l, r, num * 2 + 2)
      if x1 == None and x2 == None:
        return None
      if x1 == None:
        return x2
      if x2 == None:
        return x1
      return (min(x1[0], x2[0]), max(x1[1], x2[1]), min(x1[2], x2[2]), max(x1[3], x2[3]))

def main():
  n, d = map(int, input().split())
  stars = []
  blst = []
  for _ in range(n):
    x, y, b = map(int, input().split())
    stars.append((x, y, b))
    blst.append(b)
  blst.sort()
  stars.sort(key=lambda t:t[2])
  stars = [(x, x, y, y) for x, y, _ in stars]

  tree = SegTree(n, stars)
  ans = 0
  max_r = 0
  for l in range(n):
    r = br(blst, blst[l] + d)
    if r == n:
      r -= 1
    elif blst[r] != blst[l] + d:
      r -= 1
    if r > max_r:
      a = tree.query(l, r, 0)
      ans = max((a[1] - a[0]) * (a[3] - a[2]), ans)
      max_r = r
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br
class SegTree:
  def __init__(self, num, lst):
    num_ = 1
    while num_ < num:
      num_ *= 2
    self.length = num_ * 2 - 1
    self.arr = [None] * (num_ * 2 - 1)
    for i in range(num):
      x1, x2, y1, y2 = lst[i]
      self.arr[num_ - 1 + i] = (x1, x2, y1, y2, i, i)

    self.make(0)

  def make(self, num):
    if num >= self.length:
      return None
    if self.arr[num] != None:
      return self.arr[num]
    else:
      self.arr[num] = self.con(self.make(num * 2 + 1), self.make(num * 2 + 2))
      return self.arr[num]
  
  def con(self, n1, n2):
    if n1 != None and n2 != None:
      r0, r1, r2, r3 = self.get_min(n1[:4], n2[:4])
      return (r0, r1, r2, r3, n1[4], n2[5])
    if n1 != None:
      return n1
    if n2 != None:
      return n2
    return None

  def query(self, l, r, num):
    node = self.arr[num]
    if node == None:
      return None
    if l <= node[4] and node[5] <= r:
      return node[:4]
    elif r < node[4] or node[5] < l:
      return None
    else:
      x1 = self.query(l, r, num * 2 + 1)
      x2 = self.query(l, r, num * 2 + 2)
      if x1 == None and x2 == None:
        return None
      if x1 == None:
        return x2
      if x2 == None:
        return x1
      return self.get_min(x1, x2)
  
  def get_min(self, t1, t2):
    t10, t11, t12, t13 = t1
    t20, t21, t22, t23 = t2
    if t10 < t20:
      r0 = t10
    else:
      r0 = t20
    if t11 < t21:
      r1 = t21
    else:
      r1 = t11
    if t12 < t22:
      r2 = t12
    else:
      r2 = t22
    if t13 < t23:
      r3 = t23
    else:
      r3 = t13
    return (r0, r1, r2, r3)




def main():
  n, d = map(int, input().split())
  stars = []
  blst = []
  for _ in range(n):
    x, y, b = map(int, input().split())
    stars.append((b, x, y))
    blst.append(b)
  blst.sort()
  stars.sort()
  stars = [(x, x, y, y) for _,x, y in stars]

  tree = SegTree(n, stars)
  ans = 0
  min_l = -1
  max_r = 0
  for l in range(n):
    if min_l == l:
      continue
    min_l = l
    r = br(blst, blst[l] + d)
    if r == n:
      r -= 1
    elif blst[r] != blst[l] + d:
      r -= 1
    if r > max_r:
      a = tree.query(l, r, 0)
      ans = max((a[1] - a[0]) * (a[3] - a[2]), ans)
      max_r = r
  print(ans)
main()