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: Wrong Answer

Solution code:
from functools import reduce
from math import ceil, sqrt
from copy import copy


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

    def add(self, x, y):
        self.added = True
        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 bound.added:
            if not self.added:
                return copy(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_y: 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

    @classmethod
    def expand_list(cls, bounds):
        return reduce(cls.expand, bounds[1:], copy(bounds[0]))

    def __str__(self):
        return '({},{},{},{})'.format(self.min_x, self.min_y, self.max_x, self.max_y)


class Bucket:
    def __init__(self, bounds, unit):
        self.unit = unit
        self.bucket = [self.create_unit(bounds, i, i + unit) for i in range(0, max_b + 1, unit)]

    @staticmethod
    def create_unit(bounds, s, t):
        b = bounds[s:t]
        return (Bound.expand_list(b), b)

    def get_range(self, s, t):
        unit = self.unit
        sd, sm = s // unit, s % unit
        td, tm = t // unit, t % unit
        if sd == td:
            return Bound.expand_list(self.bucket[sd][1][sm:tm + 1])
        else:
            b_list = [b[0] for b in self.bucket[sd + 1:td]]
            bound = Bound.expand_list(b_list) if b_list else Bound()
            s_list = self.bucket[sd][1][sm:]
            if s_list:
                bound = bound.expand(Bound.expand_list(s_list))
            t_list = self.bucket[td][1][:tm + 1]
            if t_list:
                bound = bound.expand(Bound.expand_list(t_list))
            return bound


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)

if d > max_b:
    print(reduce(Bound.expand, stars[1:], stars[0]).area())
else:
    unit = ceil(sqrt(d + 1))
    if unit < 2:
        print(max(Bound.expand_list(stars[i:i + d + 1]).area() for i in range(max_b - d + 1)))
    else:
        star_buckets = Bucket(stars, unit)
        print(max(star_buckets.get_range(i + 1, i + d + 1).area() for i in range(max_b - d + 1)))

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import ceil, sqrt
from copy import copy


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

    def add(self, x, y):
        self.added = True
        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 bound.added:
            if not self.added:
                return bound.clone()
            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_y: 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

    @classmethod
    def expand_list(cls, bounds):
        return reduce(cls.expand, bounds[1:], bounds[0].clone())

    def clone(self):
        return copy(self)

    def __str__(self):
        return '({},{},{},{})'.format(self.min_x, self.min_y, self.max_x, self.max_y)


class Bucket:
    def __init__(self, bounds, unit):
        self.unit = unit
        self.bucket = [self.create_unit(bounds, i, i + unit) for i in range(0, max_b + 1, unit)]

    @staticmethod
    def create_unit(bounds, s, t):
        b = bounds[s:t]
        return (Bound.expand_list(b), b)

    def get_range(self, s, t):
        unit = self.unit
        sd, sm = s // unit, s % unit
        td, tm = t // unit, t % unit
        if sd == td:
            return Bound.expand_list(self.bucket[sd][1][sm:tm + 1])
        else:
            b_list = [b[0] for b in self.bucket[sd + 1:td]]
            bound = Bound.expand_list(b_list) if b_list else Bound()
            s_list = self.bucket[sd][1][sm:]
            if s_list:
                bound = bound.expand(Bound.expand_list(s_list))
            t_list = self.bucket[td][1][:tm + 1]
            if t_list:
                bound = bound.expand(Bound.expand_list(t_list))
            return bound


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)

if d > max_b:
    print(reduce(Bound.expand, stars[1:], stars[0]).area())
else:
    unit = ceil(sqrt(d + 1))
    if unit < 2:
        print(max(Bound.expand_list(stars[i:i + d + 1]).area() for i in range(max_b - d + 1)))
    else:
        star_buckets = Bucket(stars, unit)
        print(max(star_buckets.get_range(i, i + d + 1).area() for i in range(max_b - d + 1)))

Submission status: Wrong Answer

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
  print('test1')
  print(L)
  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])
print(L)
print(B)

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: Wrong Answer

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])))
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]))
  #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: Wrong Answer

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])))
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]))
  #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: Wrong Answer

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 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 = 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()

Submission status: Time Limit Exceeded

Solution code:
import math

class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default", "op"]

    def __init__(self, a: list, default: int, op):
        real_size = len(a)
        self.elem_size = elem_size = 1 << math.ceil(math.log2(real_size))
        self.tree = tree = [default] * (elem_size * 2)
        tree[elem_size:elem_size+real_size] = a
        self.default = default
        self.op = op

        for i in range(elem_size - 1, 0, -1):
            tree[i] = op(tree[i<<1], tree[(i<<1)+1])

    def get_value(self, x: int, y: int) -> int:
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1

        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree = self.op, self.tree
        while i > 1:
            i >>= 1
            tree[i] = op(tree[i<<1], tree[(i<<1) + 1])

if __name__ == "__main__":
    import sys
    from bisect import bisect_right

    N, d = map(int, sys.stdin.readline().split())
    b_l, x_l, y_l = zip(*sorted([(b, x, y) for l in sys.stdin.readlines() for x, y, b in (map(int, l.split()),)]))
    inf, minf = float("inf"), float("-inf")
    x_min = SegmentTree(x_l, inf, min)
    x_max = SegmentTree(x_l, minf, max)
    y_min = SegmentTree(y_l, inf, min)
    y_max = SegmentTree(y_l, minf, max)

    ans = 0
    for l, (b, _) in enumerate(zip(b_l, [-1]+list(b_l))):
        if b == _:
            continue
        r = bisect_right(b_l, b+d)
        x1, x2 = x_min.get_value(l, r), x_max.get_value(l, r)
        y1, y2 = y_min.get_value(l, r), y_max.get_value(l, r)
        ans = max(ans, (x2-x1)*(y2-y1))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class MinTree:
  def __init__(self, iterable):
    self.iter_size = self.get_size(iterable)
    self.size = self.iter_size * 2 - 1
    self.value = [None] * self.size
    for i, v in enumerate(iterable):
      self.value[self.iter_size + i - 1] = v
    self.set_value(0)
    self.range = [None] * self.size
    self.set_range(0, 0, self.iter_size - 1)
  
  def get_size(self, iterable):
    ret = 1
    x = len(iterable)
    while ret < x:
      ret *= 2
    return ret
  
  def set_range(self, x, left, right):
    self.range[x] = (left, right)
    if left != right:
      self.set_range(x * 2 + 1, left, (right + left) // 2)
      self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

  def set_value(self, x):
    if x >= self.iter_size - 1:return self.value[x]
    a = self.set_value(x * 2 + 1)
    b = self.set_value(x * 2 + 2)
    if a == None and b == None:
      self.value[x] = None
    elif a == None:
      self.value[x] = b
    elif b == None:
      self.value[x] = a
    else:
      self.value[x] = min(a, b)
    return self.value[x]

  def query(self, x, left, right):
    x_left, x_right = self.range[x]
    if right < x_left or x_right < left:
      return INF
    if left <= x_left and x_right <= right:
      return self.value[x]

    return min(self.query(x * 2 + 1, left, right), self.query(x * 2 + 2, left, right))


class MaxTree:
  def __init__(self, iterable):
    self.iter_size = self.get_size(iterable)
    self.size = self.iter_size * 2 - 1
    self.value = [None] * self.size
    for i, v in enumerate(iterable):
      self.value[self.iter_size + i - 1] = v
    self.set_value(0)
    self.range = [None] * self.size
    self.set_range(0, 0, self.iter_size - 1)
  
  def get_size(self, iterable):
    ret = 1
    x = len(iterable)
    while ret < x:
      ret *= 2
    return ret
  
  def set_range(self, x, left, right):
    self.range[x] = (left, right)
    if left != right:
      self.set_range(x * 2 + 1, left, (right + left) // 2)
      self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

  def set_value(self, x):
    if x >= self.iter_size - 1:return self.value[x]
    a = self.set_value(x * 2 + 1)
    b = self.set_value(x * 2 + 2)
    if a == None and b == None:
      self.value[x] = None
    elif a == None:
      self.value[x] = b
    elif b == None:
      self.value[x] = a
    else:
      self.value[x] = max(a, b)
    return self.value[x]

  def query(self, x, left, right):
    x_left, x_right = self.range[x]
    if right < x_left or x_right < left:
      return 0
    if left <= x_left and x_right <= right:
      return self.value[x]

    return max(self.query(x * 2 + 1, left, right), self.query(x * 2 + 2, left, right))

from bisect import bisect_right as br

n, d = map(int, input().split())
lst = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[2])
sorted_x = []
sorted_y = []
keys = []
for i in range(n):
  x, y, b = lst[i]
  sorted_x.append(x)
  sorted_y.append(y)
  keys.append(b)
mxt = MinTree(sorted_x)
Mxt = MaxTree(sorted_x)
myt = MinTree(sorted_y)
Myt = MaxTree(sorted_y)

def score(left, right):
  return (Mxt.query(0, left, right) - mxt.query(0, left, right)) * \
         (Myt.query(0, left, right) - myt.query(0, left, right))

INF = 10 ** 20
kl = 0
kr = br(keys, keys[0] + d) - 1
end = len(keys)
ans = 0
while True:
  ans = max(ans, score(kl, kr))
  kl += 1
  if kl == end:break
  while kr < end and keys[kl] + d >= keys[kr]:
    kr += 1
  kr -= 1
  if kr == end - 1:break

if kl < end and kr < end:
  ans = max(ans, score(kl, kr))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  INF = 10 ** 20

  class MinTree:
    def __init__(self, iterable):
      self.iter_size = self.get_size(iterable)
      self.size = self.iter_size * 2 - 1
      self.value = [None] * self.size
      for i, v in enumerate(iterable):
        self.value[self.iter_size + i - 1] = v
      self.set_value(0)
      self.range = [None] * self.size
      self.set_range(0, 0, self.iter_size - 1)
 
    
    def get_size(self, iterable):
      ret = 1
      x = len(iterable)
      while ret < x:
        ret *= 2
      return ret

    def set_range(self, x, left, right):
      self.range[x] = (left, right)
      if left != right:
        self.set_range(x * 2 + 1, left, (right + left) // 2)
        self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

    def set_value(self, x):
      if x >= self.iter_size - 1:return self.value[x]
      a = self.set_value(x * 2 + 1)
      b = self.set_value(x * 2 + 2)
      if a == None and b == None:
        self.value[x] = None
      elif a == None:
        self.value[x] = b
      elif b == None:
        self.value[x] = a
      else:
        self.value[x] = a if a < b else b
      return self.value[x]
  
    def query(self, x, left, right):
      x_left, x_right = self.range[x]
      if right < x_left or x_right < left:
        return INF
      if left <= x_left and x_right <= right:
        return self.value[x]
  
      return min(self.query(x * 2 + 1, left, right), self.query(x * 2 + 2, left, right))
  
  
  class MaxTree:
    def __init__(self, iterable):
      self.iter_size = self.get_size(iterable)
      self.size = self.iter_size * 2 - 1
      self.value = [None] * self.size
      for i, v in enumerate(iterable):
        self.value[self.iter_size + i - 1] = v
      self.set_value(0)
      self.range = [None] * self.size
      self.set_range(0, 0, self.iter_size - 1)
    
    def get_size(self, iterable):
      ret = 1
      x = len(iterable)
      while ret < x:
        ret *= 2
      return ret
    
    def set_range(self, x, left, right):
      self.range[x] = (left, right)
      if left != right:
        self.set_range(x * 2 + 1, left, (right + left) // 2)
        self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)


    def set_value(self, x):
      if x >= self.iter_size - 1:return self.value[x]
      a = self.set_value(x * 2 + 1)
      b = self.set_value(x * 2 + 2)
      if a == None and b == None:
        self.value[x] = None
      elif a == None:
        self.value[x] = b
      elif b == None:
        self.value[x] = a
      else:
        self.value[x] = a if a > b else b
      return self.value[x]
  
    def query(self, x, left, right):
      x_left, x_right = self.range[x]
      if right < x_left or x_right < left:
        return 0
      if left <= x_left and x_right <= right:
        return self.value[x]
  
      return max(self.query(x * 2 + 1, left, right), self.query(x * 2 + 2, left, right))
  
  from bisect import bisect_right as br

  n, d = map(int, input().split())
  lst = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[2])
  sorted_x = []
  sorted_y = []
  keys = []
  for i in range(n):
    x, y, b = lst[i]
    sorted_x.append(x)
    sorted_y.append(y)
    keys.append(b)
  mxt = MinTree(sorted_x)
  Mxt = MaxTree(sorted_x)
  myt = MinTree(sorted_y)
  Myt = MaxTree(sorted_y)
  
  def score(left, right):
    return (Mxt.query(0, left, right) - mxt.query(0, left, right)) * \
           (Myt.query(0, left, right) - myt.query(0, left, right))
  
  left = 0
  right = br(keys, keys[0] + d) - 1
  mx = mxt.query(0, left, right)
  Mx = Mxt.query(0, left, right)
  my = myt.query(0, left, right)
  My = Myt.query(0, left, right)
  end = len(keys)
  ans = (Mx - mx) * (My - my)
  while True:
    right += 1
    if right == end:break
    
    if sorted_x[right] > Mx:Mx = sorted_x[right]
    if sorted_x[right] < mx:mx = sorted_x[right] 
    if sorted_y[right] > My:My = sorted_y[right]
    if sorted_y[right] < my:my = sorted_y[right]
    
    Mx_flag = mx_flag = My_flag = my_flag = False
    while keys[left] + d < keys[right]:
      if sorted_x[left] == Mx:Mx_flag = True
      if sorted_x[left] == mx:mx_flag = True
      if sorted_y[left] == My:My_flag = True
      if sorted_y[left] == my:my_flag = True
      left += 1
    
    if Mx_flag:Mx = Mxt.query(0, left, right)
    if mx_flag:mx = mxt.query(0, left, right)
    if My_flag:My = Myt.query(0, left, right)
    if my_flag:my = myt.query(0, left, right)
    
    ans = max(ans, (Mx - mx) * (My - my)) 
  
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  INF = 10 ** 20

  class MinTree:
    def __init__(self, iterable):
      self.iter_size = self.get_size(iterable)
      self.size = self.iter_size * 2 - 1
      self.value = [None] * self.size
      for i, v in enumerate(iterable):
        self.value[self.iter_size + i - 1] = v
      self.set_value(0)
      #self.range = [None] * self.size
      #self.set_range(0, 0, self.iter_size - 1)
    
    def get_size(self, iterable):
      ret = 1
      x = len(iterable)
      while ret < x:
        ret *= 2
      return ret

    def set_range(self, x, left, right):
      self.range[x] = (left, right)
      if left != right:
        self.set_range(x * 2 + 1, left, (right + left) // 2)
        self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

    def set_value(self, x):
      if x >= self.iter_size - 1:return self.value[x]
      a = self.set_value(x * 2 + 1)
      b = self.set_value(x * 2 + 2)
      if a == None and b == None:
        self.value[x] = None
      elif a == None:
        self.value[x] = b
      elif b == None:
        self.value[x] = a
      else:
        self.value[x] = a if a < b else b
      return self.value[x]
  
    def query(self, x, left, right):
      x_left, x_right = self.range[x]
      if right < x_left or x_right < left:
        return INF
      if left <= x_left and x_right <= right:
        return self.value[x]
      a = self.query(x * 2 + 1, left, right)
      b = self.query(x * 2 + 2, left, right)
      return a if a <= b else b
 
  class MaxTree:
    def __init__(self, iterable):
      self.iter_size = self.get_size(iterable)
      self.size = self.iter_size * 2 - 1
      self.value = [None] * self.size
      for i, v in enumerate(iterable):
        self.value[self.iter_size + i - 1] = v
      self.set_value(0)
      #self.range = [None] * self.size
      #self.set_range(0, 0, self.iter_size - 1)
    
    def get_size(self, iterable):
      ret = 1
      x = len(iterable)
      while ret < x:
        ret *= 2
      return ret
    
    def set_range(self, x, left, right):
      self.range[x] = (left, right)
      if left != right:
        self.set_range(x * 2 + 1, left, (right + left) // 2)
        self.set_range(x * 2 + 2, (right + left) // 2 + 1, right)

    def set_value(self, x):
      if x >= self.iter_size - 1:return self.value[x]
      a = self.set_value(x * 2 + 1)
      b = self.set_value(x * 2 + 2)
      if a == None and b == None:
        self.value[x] = None
      elif a == None:
        self.value[x] = b
      elif b == None:
        self.value[x] = a
      else:
        self.value[x] = a if a > b else b
      return self.value[x]
  
    def query(self, x, left, right):
      x_left, x_right = self.range[x]
      if right < x_left or x_right < left:
        return 0
      if left <= x_left and x_right <= right:
        return self.value[x]
      a = self.query(x * 2 + 1, left, right)
      b = self.query(x * 2 + 2, left, right)
      return a if a >= b else b
  
  def set_range(lst, x, left, right):
    lst[x] = (left, right)
    if left != right:
      set_range(lst, x * 2 + 1, left, (right + left) // 2)
      set_range(lst, x * 2 + 2, (right + left) // 2 + 1, right)
 


  from bisect import bisect_right as br

  n, d = map(int, input().split())
  lst = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[2])
  sorted_x = []
  sorted_y = []
  keys = []
  for i in range(n):
    x, y, b = lst[i]
    sorted_x.append(x)
    sorted_y.append(y)
    keys.append(b)
  mxt = MinTree(sorted_x)
  Mxt = MaxTree(sorted_x)
  myt = MinTree(sorted_y)
  Myt = MaxTree(sorted_y)
  lst = [None] * mxt.size
  set_range(lst, 0, 0, mxt.iter_size - 1)
  mxt.range = lst
  Mxt.range = lst
  myt.range = lst
  Myt.range = lst
  
  def score(left, right):
    return (Mxt.query(0, left, right) - mxt.query(0, left, right)) * \
           (Myt.query(0, left, right) - myt.query(0, left, right))
  
  left = 0
  right = br(keys, keys[0] + d) - 1
  mx = mxt.query(0, left, right)
  Mx = Mxt.query(0, left, right)
  my = myt.query(0, left, right)
  My = Myt.query(0, left, right)
  end = len(keys)
  ans = (Mx - mx) * (My - my)
  Mx_flag = mx_flag = My_flag = my_flag = False
  while True:
    right += 1
    if right == end:break
    
    if sorted_x[right] > Mx:Mx = sorted_x[right]
    if sorted_x[right] < mx:mx = sorted_x[right] 
    if sorted_y[right] > My:My = sorted_y[right]
    if sorted_y[right] < my:my = sorted_y[right]
    
    while keys[left] + d < keys[right]:
      if sorted_x[left] == Mx:Mx_flag = True
      if sorted_x[left] == mx:mx_flag = True
      if sorted_y[left] == My:My_flag = True
      if sorted_y[left] == my:my_flag = True
      left += 1
    
    if Mx_flag:
      Mx = Mxt.query(0, left, right)
      Mx_flag = False
    if mx_flag:
      mx = mxt.query(0, left, right)
      mx_flag = False
    if My_flag:
      My = Myt.query(0, left, right)
      My_flag = False
    if my_flag:
      my = myt.query(0, left, right)
      my_flag = False
    
    ans = max(ans, (Mx - mx) * (My - my)) 
  
  print(ans)

main()