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:
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_left as bl

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_to_ind = {}
for i in range(n):
  x, y, b = lst[i]
  sorted_x.append(x)
  sorted_y.append(y)
  keys_to_ind[b] = i
keys = list(keys_to_ind.keys())

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 = bl(keys, keys[0] + d)
end = len(keys)
ans = 0
while kr < end:
  ans = max(ans, score(keys_to_ind[keys[kl]], keys_to_ind[keys[kr]]))
  kl += 1
  while keys[kl] + d >= keys[kr]:
    kr += 1
    if kr == end:break
  else:
    kr -= 1
print(ans)

Submission status: Wrong Answer

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_left as bl

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_to_ind = {}
for i in range(n):
  x, y, b = lst[i]
  sorted_x.append(x)
  sorted_y.append(y)
  if b not in keys_to_ind:
    keys_to_ind[b] = i
keys = list(keys_to_ind.keys())
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 = bl(keys, keys[0] + d)
end = len(keys)
ans = 0
while kr < end:
  ans = max(ans, score(keys_to_ind[keys[kl]], keys_to_ind[keys[kr]]))
  kl += 1
  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(keys_to_ind[keys[kl]], keys_to_ind[keys[kr]]))
print(ans)

Submission status: Wrong Answer

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) - 2
  mx = mxt.query(0, left, right)
  Mx = Mxt.query(0, left, right)
  my = myt.query(0, left, right)
  My = Myt.query(0, left, right)
  mxf = Mxf = myf = Myf = False
  end = len(keys)
  ans = 0
  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
    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)) 
  
  if left < end and right < end:
    ans = max(ans, score(left, right))
  print(ans)

main()

Submission status: Wrong Answer

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

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

Solution code:
import math
def segmentTree(dat, f, sentinel):
        pad = 2 ** math.ceil(math.log(len(dat),2))
        dat = [0] * pad + dat + [sentinel] * (pad - len(dat))
        for i in range(pad - 1, 0, -1):
            dat[i] = f(dat[i * 2:i * 2 + 2])
        return dat

def get_lr(b,d):
    l = r = 0
    while r < len(b):
        while b[l] + d < b[r]:
            l += 1
        for r in range(r,len(b)):
            if b[l] + d < b[r]:
                r -= 1
                break
        r += 1
        yield l,r
        l += 1
    
import sys
f = sys.stdin


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

xyb = []
for line in f:
    xyb.append(tuple(map(int, line.split())))
from operator import itemgetter
xyb.sort(key=itemgetter(2))

x = [xybi[0] for xybi in xyb]
y = [xybi[1] for xybi in xyb]
b = [xybi[2] for xybi in xyb]

xmax = segmentTree(x,max,sentinel = 0)
xmin = segmentTree(x,min,sentinel = 2000000)
ymax = segmentTree(y,max,sentinel = 0)
ymin = segmentTree(y,min,sentinel = 2000000)


size = []
sa = size.append #万単位で呼び出す場合は若干早くなる
pad = len(xmax) // 2
max_size = 0
m = pad
pre_xmax,pre_xmin,pre_ymax,pre_ymin=0,0,0,0
def create_index(l,r):
    index = []
    ia = index.append
    while l < r:
        if r & 1:
            r -= 1
            ia(r)
        if l & 1:
            ia(l)
            l += 1
        l >>= 1
        r >>= 1
    return index

for l,r in get_lr(b,d):
    # 参照するsegmentのindexを生成　※速度のためインライン展開
    l += pad 
    r += pad
    index = create_index(m,r)

    now_xmax = max(xmax[i] for i in index)
    now_xmin = min(xmin[i] for i in index)
    now_ymax = max(ymax[i] for i in index)
    now_ymin = min(ymin[i] for i in index)
    
    if pre_xmax < now_xmax or pre_xmin > now_xmin or pre_ymax < now_ymax or pre_ymin > now_ymin:
        if l < m:
            index = create_index(l,m)
            now_xmax = max(now_xmax,max(xmax[i] for i in index))
            now_xmin = min(now_xmin,min(xmin[i] for i in index))
            now_ymax = max(now_ymax,max(ymax[i] for i in index))
            now_ymin = min(now_ymin,min(ymin[i] for i in index))

        size = (now_xmax - now_xmin) * (now_ymax - now_ymin)
        if max_size < size:
            max_size = size
            pre_xmax,pre_xmin,pre_ymax,pre_ymin=now_xmax,now_xmin,now_ymax,now_ymin
    m = r
print(max_size)

Submission status: Wrong Answer

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
for j in range(len(a)):
    minlight = a[0][2]
    astars = []
    for k in range(len(a)):
        while(len(astars)<=2):
            if (a[k][2] >= minlight and a[k][2] <= minlight + lightrange):
                astars.append(a[k])
                twostars = k
    maxx = max(astars[0][0],astars[1][0])
    minx = min(astars[0][0],astars[1][0])
    maxy = max(astars[0][1],astars[1][1])
    miny = min(astars[0][1],astars[1][1])
    for l in range(twostars+1,len(a)):
        if (a[l][2] >= minlight and a[l][2] <= minlight + lightrange and (a[l][0]<minx or a[l][0]>maxx or a[l][1]<miny or a[l][1]>maxy)):
            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][0]>maxy):
                maxy=a[l][1]
    area = (maxx-minx)*(maxy-miny)
    if (area > scale):
        scale = area
    del a[0]
    if len(a) < 2:
        break;

print scale

Submission status: Wrong Answer

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
for j in range(len(a)):
    astars = []
    for k in range(len(a)):
        while(len(astars)<=2):
            if (a[k][2] <= a[0][2] + lightrange):
                astars.append(a[k])
                twostars = k
    maxx = max(astars[0][0],astars[1][0])
    minx = min(astars[0][0],astars[1][0])
    maxy = max(astars[0][1],astars[1][1])
    miny = min(astars[0][1],astars[1][1])
    for l in range(len(a)):
        if (a[l][2] <= a[0][2] + lightrange and (a[l][0]<minx or a[l][0]>maxx or a[l][1]<miny or a[l][1]>maxy)):
            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][0]>maxy):
                maxy=a[l][1]
    area = (maxx-minx)*(maxy-miny)
    if (area > scale):
        scale = area
    del a[0]
    if len(a) < 2:
        break;

print scale

Submission status: Wrong Answer

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
    if (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]
    area = (maxx-minx)*(maxy-miny)
    if (area > scale):
        scale = area
    del a[0]
print scale

Submission status: Wrong Answer

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):
    if(a[0][2] + lightrange < a[1][2]):
        break;
    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])
        if k==len(a)-1:
            break;
        print "!"
        k+=1
    area = (maxx-minx)*(maxy-miny)
    scale = max(scale,area)
    del a[0]
    print "?"
print scale

Submission status: Wrong Answer

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()))
x = [a[p][0] for p in range(stars)]
y = [a[q][1] for q in range(stars)]
light = [a[r][2] for r in range(stars)]
x.sort()
y.sort()
light.sort()
X=Y=[]
k=scale=0
for j in range(stars):
    while(a[k][2] < a[j][2]-lightrange):
        X.remove(x[k])
        Y.remove(y[k])
        k+=1
    X.append(x[j])
    Y.append(y[j])
    scale = max(scale, (X[len(X)-1]-X[0])*(Y[len(Y)-1]-Y[0]))
print scale

Submission status: Wrong Answer

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)

d = min(d, max_b)

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