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: Runtime Error

Solution code:
from math import ceil
class sqrt_tree:
    def __init__(self,dat,f):
        self.dat = dat
        self.sq = int(len(dat) ** 0.5)
        self.f = f
        self.baqet = [self.f(dat[i * self.sq:(i + 1) * self.sq]) for i in range(self.sq)]
    
    #query
    def q(self,l,r):
        r += 1
        if ceil(l / self.sq) >= r // self.sq:
            return self.f(self.dat[l:r])
        ret = self.f(self.baqet[ceil(l / self.sq):r // self.sq])
        if l % self.sq:
            ret = self.f(ret,self.f(self.dat[l:l + self.sq]))
        if r % self.sq:
            ret = self.f(ret,self.f(self.dat[r - r % self.sq:r]))
        return ret

import sys
f = sys.stdin

_, d = map(int, f.readline().split())

x,y = {},{}
for line in f:
    xi, yi, bi = map(int, line.split())
    if bi not in x:
        x[bi],y[bi] = [],[]
    x[bi].append(xi)
    y[bi].append(yi)

b = sorted(x.keys())

xmax = sqrt_tree([max(x[bi]) for bi in b],max)
xmin = sqrt_tree([min(x[bi]) for bi in b],min)
ymax = sqrt_tree([max(y[bi]) for bi in b],max)
ymin = sqrt_tree([min(y[bi]) for bi in b],min)

def get_lr(b,d):
    l = r = 0
    while r < len(b) - 1:
        for k in range(r,-1,-1):
            if b[k] + d < b[r]:
                break
            l = k
        for k in range(l,len(b)):
            if b[l] + d < b[k]:
                break
            r = k
        yield l,r
        r += 1
   
max_size = max((xmax.q(l,r) - xmin.q(l,r)) * (ymax.q(l,r) - ymin.q(l,r)) for l,r in get_lr(b,d))
print(max_size)

Submission status: Runtime Error

Solution code:
from math import ceil
class sqrt_tree:
    def __init__(self,dat,f):
        self.dat = dat
        self.sq = int(len(dat) ** 0.5)
        self.f = f
        self.baqet = [self.f(dat[i * self.sq:(i + 1) * self.sq]) for i in range(self.sq)]
    
    #query
    def q(self,l,r):
        r += 1
        if ceil(l / self.sq) >= r // self.sq:
            return self.f(self.dat[l:r])
        ret = self.f(self.baqet[ceil(l / self.sq):r // self.sq])
        if l % self.sq:
            ret = self.f(ret,self.f(self.dat[l:l + self.sq]))
        if r % self.sq:
            ret = self.f(ret,self.f(self.dat[r - r % self.sq:r]))
        return ret

import sys
f = sys.stdin

_, d = map(int, f.readline().split())

x,y = {},{}
for line in f:
    xi, yi, bi = map(int, line.split())
    if bi not in x:
        x[bi],y[bi] = [],[]
    x[bi].append(xi)
    y[bi].append(yi)

b = sorted(x.keys())

xmax = sqrt_tree([max(x[bi]) for bi in b],max)
xmin = sqrt_tree([min(x[bi]) for bi in b],min)
ymax = sqrt_tree([max(y[bi]) for bi in b],max)
ymin = sqrt_tree([min(y[bi]) for bi in b],min)

def get_lr(b,d):
    l = r = 0
    while r < len(b) - 1:
        while b[l] + d < b[r]:
            l += 1
        for k in range(l,len(b)):
            if b[l] + d < b[k]:
                break
            r = k
        yield l,r
        r += 1
        l += 1
   
max_size = max((xmax.q(l,r) - xmin.q(l,r)) * (ymax.q(l,r) - ymin.q(l,r)) for l,r in get_lr(b,d))
print(max_size)

Submission status: Runtime Error

Solution code:
data = map(int, raw_input().split())
stars = data[0]
lightrange = data[1]
a = []
for i in range(stars):
    a.append(map(int, raw_input().split()))
a.sort(key=lambda x:x[2])
scale = 0
while(len(a)>1):
    minx=maxx=a[0][0]
    miny=maxy=a[0][1]
    k=1
    while(a[k][2]<=a[0][2] + lightrange):
        if (a[k][0]<minx or a[k][0]>maxx or a[k][1]<miny or a[k][1]>maxy):
            minx = min(minx,a[k][0])
            maxx = max(maxx,a[k][0])
            miny = min(miny,a[k][1])
            maxy = max(maxy,a[k][1])
        k+=1
    area = (maxx-minx)*(maxy-miny)
    scale = max(scale,area)
    del a[0]
print scale

Submission status: Runtime Error

Solution code:
data = map(int, raw_input().split())
stars = data[0]
lightrange = data[1]
a = []
for i in range(stars):
    a.append(map(int, raw_input().split()))
a.sort(key=lambda x:x[2])
scale = 0
try:
    while(len(a)>1):
        minx=maxx=a[0][0]
        miny=maxy=a[0][1]
        k=1
        while(a[k][2]<=a[0][2] + lightrange):
            if (a[k][0]<minx or a[k][0]>maxx or a[k][1]<miny or a[k][1]>maxy):
                minx = min(minx,a[k][0])
                maxx = max(maxx,a[k][0])
                miny = min(miny,a[k][1])
                maxy = max(maxy,a[k][1])
            k+=1
        area = (maxx-minx)*(maxy-miny)
        scale = max(scale,area)
        del a[0]
except(RuntimeError):
    pass
print scale

Submission status: Runtime Error

Solution code:
data = map(int, raw_input().split())
stars = data[0]
lightrange = data[1]
a = []
for i in range(stars):
    a.append(map(int, raw_input().split()))
a.sort(key=lambda x:x[2])
scale = 0
while(len(a)>1):
    minx=maxx=a[0][0]
    miny=maxy=a[0][1]
    k=1
    while(a[k][2]<=a[0][2] + lightrange):
        if (a[k][0]<minx or a[k][0]>maxx or a[k][1]<miny or a[k][1]>maxy):
            minx = min(minx,a[k][0])
            maxx = max(maxx,a[k][0])
            miny = min(miny,a[k][1])
            maxy = max(maxy,a[k][1])
        k+=1
    area = (maxx-minx)*(maxy-miny)
    scale = max(scale,area)
    del a[0]
    if(len(a)<2):
        break;
print scale

Submission status: Runtime Error

Solution code:
data = map(int, raw_input().split())
stars = data[0]
lightrange = data[1]
a = []
for i in range(stars):
    a.append(map(int, raw_input().split()))
a.sort(key=lambda x:x[2])
scale = 0
while(len(a)>1):
    minx=maxx=a[0][0]
    miny=maxy=a[0][1]
    k=1
    while(a[k][2]<=a[0][2] + lightrange):
        if (a[k][0]<minx or a[k][0]>maxx or a[k][1]<miny or a[k][1]>maxy):
            minx = min(minx,a[k][0])
            maxx = max(maxx,a[k][0])
            miny = min(miny,a[k][1])
            maxy = max(maxy,a[k][1])
        k+=1
    area = (maxx-minx)*(maxy-miny)
    #scale = max(scale,area)
    if(area>scale):
        scale = area
    del a[0]
print scale

Submission status: Runtime Error

Solution code:
data = map(int, raw_input().split())
stars = data[0]
lightrange = data[1]
a = []
for i in range(stars):
    a.append(map(int, raw_input().split()))
a.sort(key=lambda x:x[2])
scale = 0
while(len(a)>1):
    minx=maxx=a[0][0]
    miny=maxy=a[0][1]
    l=1
    while (a[l][2] <= a[0][2] + lightrange):
        if(a[l][0]<minx):
            minx=a[l][0]
        if(a[l][0]>maxx):
            maxx=a[l][0]
        if(a[l][1]<miny):
            miny=a[l][1]
        if(a[l][1]>maxy):
            maxy=a[l][1]
        l+=1
    area = (maxx-minx)*(maxy-miny)
    if (area > scale):
        scale = area
    del a[0]
print scale

Submission status: Runtime Error

Solution code:
data = map(int, raw_input().split())
stars = data[0]
lightrange = data[1]
a = []
for i in range(stars):
    a.append(map(int, raw_input().split()))
a.sort(key=lambda x:x[2])
scale = []
while(len(a)>1):
    k=0
    x=[]
    y=[]
    while(a[k][2]<=a[0][2] + lightrange):
        x.append(a[k][0])
        y.append(a[k][1])
        k+=1
        if(k==len(a)):
            break
    scale.append((max(x)-min(x))*(max(y)-min(y)))
    del a[0]
print max(scale)

Submission status: Runtime Error

Solution code:
data = map(int, raw_input().split())
stars = data[0]
lightrange = data[1]
a = []
for i in range(stars):
    a.append(map(int, raw_input().split()))
a.sort(key=lambda x:x[2])
scale = []
minlight = -1
while(len(a)>1):
    if a[0] == minlight:
        del a[0]
    else :
        k=0
        x=[]
        y=[]
        while(a[k][2]<=a[0][2] + lightrange):
            x.append(a[k][0])
            y.append(a[k][1])
            k+=1
            if(k==len(a)):
                break
        scale.append((max(x)-min(x))*(max(y)-min(y)))
        minlight = a[0][2]
        del a[0]
print max(scale)

Submission status: Runtime Error

Solution code:
data = map(int, raw_input().split())
stars = data[0]
lightrange = data[1]
a = []
for i in range(stars):
    a.append(map(int, raw_input().split()))
a.sort(key=lambda x:x[2])
scale = []
minlight = -1
while(len(a)>1):
    if a[0] == minlight:
        del a[0]
    else :
        k=0
        x=[]
        y=[]
        while(a[k][2]<=a[0][2] + lightrange):
            x.append(a[k][0])
            y.append(a[k][1])
            k+=1
            if(k==len(a)):
                break
        scale.append((max(x)-min(x))*(max(y)-min(y)))
        minlight = a[0][2]
        del a[0]
    if len(a)==1:
        break
print max(scale)

Submission status: Runtime Error

Solution code:
from functools import reduce


class Bound:
    min_x = 2000001
    min_y = 2000001
    max_x = -1
    max_y = -1

    def add(self, x, y):
        if self.min_x > x: self.min_x = x
        if self.min_y > y: self.min_y = y
        if self.max_x < x: self.max_x = x
        if self.max_y < y: self.max_y = y

    def expand(self, bound):
        if self.min_x > bound.min_x: self.min_x = bound.min_x
        if self.min_y > bound.min_y: self.min_y = bound.min_y
        if self.max_x < bound.max_x: self.max_x = bound.max_x
        if self.max_y < bound.max_x: self.max_y = bound.max_y
        return self

    def area(self):
        return (self.max_x - self.min_x) * (self.max_y - self.min_y) if self.max_x > -1 else 0


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 = [Bound() for _ in range(max_b + 1)]
for x, y, b in input_store:
    stars[b].add(x, y)

print(max(reduce(Bound.expand, stars[i + 1:i + d + 1], stars[i]).area() for i in range(max_b - d + 1)))

Submission status: Runtime Error

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:1] 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: Runtime Error

Solution code:
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]
    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: Runtime Error

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([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: Runtime Error

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([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: Runtime Error

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(set([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: Runtime Error

Solution code:
from sys import stdin
from operator import itemgetter as it
D={}
result=[]
_,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(max(result))

Submission status: Runtime Error

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 len==(result) else max(result))

Submission status: Runtime Error

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:result.append((max(map(it(0),l))-min(map(it(0),l)))*(max(map(it(1),l))-min(map(it(1),l))))
print(max(result))

Submission status: Runtime Error

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

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 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])))
print('test1')
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]))
  if result < s:result = s
  if b > Max:break
print(result)

Submission status: Runtime Error

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)))
          ))))
    #L3 = tuple(zip(*L2))
    s = (max(L3[1]) - min(L3[0])) * (max(L3[3]) - min(L3[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: Runtime Error

Solution code:
from bisect import bisect_left as bl

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 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 = bl(blst, blst[l] + d)
    if r >= n:
      r -= 1
    a = tree.query(l, r, 0).val
    ans = max((a[1] - a[0]) * (a[3] - a[2]), ans)
  print(ans)
main()