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:
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)
    
    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)
    
    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)

  def index_of_query(lst, x, left, right, ret):
    x_left, x_right = lst[x]
    if right < x_left or x_right < left:pass
    elif left <= x_left and x_right <= right:
      ret.append(x)
    else:
      index_of_query(lst, x * 2 + 1, left, right, ret)
      index_of_query(lst, x * 2 + 2, left, right, ret)



  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
    
    ret = []
    index_of_query(lst, 0, left, right, ret)
    if Mx_flag:
      #Mx = Mxt.query(0, left, right)
      Mx = max(Mxt.value[i] for i in ret)
      Mx_flag = False
    if mx_flag:
      #mx = mxt.query(0, left, right)
      mx = min(mxt.value[i] for i in ret)
      mx_flag = False
    if My_flag:
      #My = Myt.query(0, left, right)
      My = max(Myt.value[i] for i in ret)
      My_flag = False
    if my_flag:
      my = myt.query(0, left, right)
      my = min(myt.value[i] for i in ret)
      my_flag = False
    
    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)
    
    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)
    
    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)

  def index_of_query(lst, x, left, right, ret):
    x_left, x_right = lst[x]
    if right < x_left or x_right < left:pass
    elif left <= x_left and x_right <= right:
      ret.append(x)
    else:
      index_of_query(lst, x * 2 + 1, left, right, ret)
      index_of_query(lst, x * 2 + 2, left, right, ret)



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

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

  def index_of_query(lst, x, left, right, ret):
    x_left, x_right = lst[x]
    if right < x_left or x_right < left:pass
    elif left <= x_left and x_right <= right:
      ret.append(x)
    else:
      index_of_query(lst, x * 2 + 1, left, right, ret)
      index_of_query(lst, x * 2 + 2, left, right, ret)



  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
    
    ret = []
    index_of_query(lst, 0, left, right, ret)
    if Mx_flag:
      Mx = max(Mxt.value[i] for i in ret)
      Mx_flag = False
    if mx_flag:
      mx = min(mxt.value[i] for i in ret)
      mx_flag = False
    if My_flag:
      My = max(Myt.value[i] for i in ret)
      My_flag = False
    if my_flag:
      my = min(myt.value[i] for i in ret)
      my_flag = False
    
    ans = max(ans, (Mx - mx) * (My - my)) 
  
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
f = sys.stdin

def mix(a,b):
    return (min(a[0],b[0]),min(a[1],b[1]),max(a[2],b[2]),max(a[3],b[3]))

s = {}

n, d = map(int, f.readline().split())
for _ in range(n):
    x, y, b = map(int, f.readline().split())
    s[b] = mix(s[b],(x,y,x,y)) if b in s else (x,y,x,y)

max_size = 0
b = sorted(s.keys())
for i in range(len(b)):
    xy = s[b[i]]
    for j in range(i + 1,len(b)):
        if b[i] + d < b[j]:
            break
        xy = mix(xy,s[b[j]])
    max_size = max(max_size,((xy[2] - xy[0]) * (xy[3] - xy[1])))
print(max_size)

Submission status: Time Limit Exceeded

Solution code:
import sys
f = sys.stdin

def mix(a,b):
    return (min(a[0],b[0]),min(a[1],b[1]),max(a[2],b[2]),max(a[3],b[3]))

s = {}

n, d = map(int, f.readline().split())
for _ in range(n):
    x, y, b = map(int, f.readline().split())
    s[b] = mix(s[b],(x,y,x,y)) if b in s else (x,y,x,y)

max_size = 0
b = sorted(s.keys())
i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k] + d < b[j]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i] + d < b[k]:
            break
        j = k
    
    xy = s[b[i]]
    for k in range(i + 1, j + 1):
        xy = mix(xy,s[b[k]])
    
    max_size = max(max_size,((xy[2] - xy[0]) * (xy[3] - xy[1])))
    j+=1
    
print(max_size)

Submission status: Time Limit Exceeded

Solution code:
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())

xmin,xmax,ymin,ymax = [None for _ in range(len(b))],[None for _ in range(len(b))],[None for _ in range(len(b))],[None for _ in range(len(b))]
for i in range(len(b)):
    xmin[i],xmax[i],ymin[i],ymax[i] = min(x[b[i]]),max(x[b[i]]),min(y[b[i]]),max(y[b[i]])

max_size = i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k] + d < b[j]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i] + d < b[k]:
            break
        j = k
    size = (max(xmax[i:j + 1]) - min(xmin[i:j + 1])) * (max(ymax[i:j + 1]) - min(ymin[i:j + 1]))
    max_size = max(max_size,size)
    j+=1
    
print(max_size)

Submission status: Time Limit Exceeded

Solution code:
import sys
f = sys.stdin

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

x,y,b = [],[],set()
for line in f:
    xi, yi, bi = map(int, line.split())
    x.append((xi,bi))
    y.append((yi,bi))
    b.update([bi])    
x = sorted(x)
y = sorted(y)
b = sorted(b)


def search(target,bmin,bmax):
    tmax,tmin = None,None
    for i in range(len(target)):
        if bmin <= target[i][1] <= bmax:
            tmin = target[i][0]
            break
    for i in range(len(target) - 1, -1, -1):
        if bmin <= target[i][1] <= bmax:
            tmax = target[i][0]
            break
    return tmax,tmin
    

max_size = i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k] + d < b[j]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i] + d < b[k]:
            break
        j = k

    xmax,xmin = search(x,b[i],b[j])
    ymax,ymin = search(y,b[i],b[j])
    
    max_size = max(max_size,(xmax - xmin) * (ymax - ymin))
    j+=1
    
print(max_size)

Submission status: Time Limit Exceeded

Solution code:
import math
class SegmentTree:
    def __init__(self, dat, func, sentinel):
        self.pad = 2 ** math.ceil(math.log(len(dat),2)) - 1
        self.dat = [None] * self.pad + dat + [sentinel] * (self.pad + 1 - len(dat))
        self.func = func
        self.sentinel = sentinel
        for i in range(self.pad - 1, -1, -1):
            self.dat[i] = self.func(self.dat[i * 2 + 1],self.dat[i * 2 + 2])
        
    def q(self,s,e):
        return self._q(self.pad + s,self.pad + e,0,self.pad,len(self.dat) - 1)
    def _q(self,a,b,k,l,r):
        if b < l or r < a:
            return self.sentinel
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self._q(a,b,k * 2 + 1,l,(l+r)//2)
            vr = self._q(a,b,k * 2 + 2,(l+r)//2 + 1,r)
            return self.func(vl,vr)
import sys
f = sys.stdin

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

b = []
for line in f:
    xi, yi, bi = map(int, line.split())
    b.append((bi,xi,yi))
b = sorted(b)
x = [xi for _,xi,_ in b]
y = [yi for _,_,yi in b]


        
minx = SegmentTree(x,min,sentinel = 2000001)
maxx = SegmentTree(x,max,sentinel = -1)
miny = SegmentTree(y,min,sentinel = 2000001)
maxy = SegmentTree(y,max,sentinel = -1)


max_size = i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k][0] + d < b[j][0]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i][0] + d < b[k][0]:
            break
        j = k
    
    max_size = max(max_size,(maxx.q(i,j) - minx.q(i,j)) * (maxy.q(i,j) - miny.q(i,j)))
    j+=1
    
print(max_size)

Submission status: Time Limit Exceeded

Solution code:
import sys
f = sys.stdin

def q(t,s,e,func):
    if s == e:
        return t[s]
    else:
        return func(q(t,s,(s+e)//2,func),q(t,(s+e)//2 + 1,e,func))

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

b = []
for line in f:
    xi, yi, bi = map(int, line.split())
    b.append((bi,xi,yi))
b = sorted(b)
x = tuple(xi for _,xi,_ in b)
y = tuple(yi for _,_,yi in b)

max_size = i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k][0] + d < b[j][0]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i][0] + d < b[k][0]:
            break
        j = k

    max_size = max(max_size,(q(x,i,j,max) - q(x,i,j,min)) * (q(y,i,j,max) - q(y,i,j,min)))
    j+=1
    
print(max_size)

Submission status: Time Limit Exceeded

Solution code:
import sys
f = sys.stdin


def memoize(f):
  memo = {}
  def inner(v1,v2,v3,v4):
      if not (v1,v2,v3,v4) in memo:
        memo[v1,v2,v3,v4] = f(v1,v2,v3,v4)
      return memo[v1,v2,v3,v4]
  return inner

@memoize
def q(t,s,e,func):
    if s == e:
        return t[s]
    else:
        return func(q(t,s,(s+e)//2,func),q(t,(s+e)//2 + 1,e,func))

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

b = []
for line in f:
    xi, yi, bi = map(int, line.split())
    b.append((bi,xi,yi))
b = sorted(b)
x = tuple(xi for _,xi,_ in b)
y = tuple(yi for _,_,yi in b)

max_size = i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k][0] + d < b[j][0]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i][0] + d < b[k][0]:
            break
        j = k

    max_size = max(max_size,(q(x,i,j,max) - q(x,i,j,min)) * (q(y,i,j,max) - q(y,i,j,min)))
    j+=1
    
print(max_size)

Submission status: Time Limit Exceeded

Solution code:
import sys
f = sys.stdin

def q(t,i,s,e,func):
    if s == e:
        return t[s][i]
    else:
        return func(q(t,i,s,(s+e)//2,func),q(t,i,(s+e)//2 + 1,e,func))

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

b = []
for line in f:
    xi, yi, bi = map(int, line.split())
    b.append((bi,xi,yi))
b = sorted(b)

max_size = i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k][0] + d < b[j][0]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i][0] + d < b[k][0]:
            break
        j = k

    max_size = max(max_size,(q(b,1,i,j,max) - q(b,1,i,j,min)) * (q(b,2,i,j,max) - q(b,2,i,j,min)))
    j+=1
    
print(max_size)

Submission status: Time Limit Exceeded

Solution code:
import math
class SegmentTree:
    def __init__(self, dat, func, sentinel):
        self.pad = 2 ** math.ceil(math.log(len(dat),2)) - 1
        self.dat = [None] * self.pad + dat + [sentinel] * (self.pad + 1 - len(dat))
        self.func = func
        self.sentinel = sentinel
        for i in range(self.pad - 1, -1, -1):
            self.dat[i] = self.func(self.dat[i * 2 + 1],self.dat[i * 2 + 2])
        
    def q(self,s,e):
        return self._q(self.pad + s,self.pad + e,0,self.pad,len(self.dat) - 1)
    def _q(self,a,b,k,l,r):
        if b < l or r < a:
            return self.sentinel
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self._q(a,b,k * 2 + 1,l,(l+r)//2)
            vr = self._q(a,b,k * 2 + 2,(l+r)//2 + 1,r)
            return self.func(vl,vr)
import sys
f = sys.stdin


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

#内包表記にしないと速度不足
b = sorted([list(map(int, line.split()))[::-1] for line in f])
x = [bi[2] for bi in b]
y = [bi[1] for bi in b]


        
minx = SegmentTree(x,min,sentinel = 2000001)
maxx = SegmentTree(x,max,sentinel = -1)
miny = SegmentTree(y,min,sentinel = 2000001)
maxy = SegmentTree(y,max,sentinel = -1)

max_size = i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k][0] + d < b[j][0]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i][0] + d < b[k][0]:
            break
        j = k
    
    max_size = max(max_size,(maxx.q(i,j) - minx.q(i,j)) * (maxy.q(i,j) - miny.q(i,j)))
    j+=1
    
print(max_size)

Submission status: Time Limit Exceeded

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.baqet = {}
        for fi in f:
            self.baqet[fi] = [fi(dat[i * self.sq:(i + 1) * self.sq]) for i in range(self.sq)]
    
    #query
    def q(self,f,l,r):
        r += 1
        if ceil(l / self.sq) >= r // self.sq:
            return f(self.dat[l:r])
        ret = f(self.baqet[f][ceil(l / self.sq):r // self.sq])
        if l % self.sq:
            ret = f(ret,f(self.dat[l:l + self.sq]))
        if r % self.sq:
            ret = f(ret,f(self.dat[r - r % self.sq:r]))
        return ret

import sys
f = sys.stdin

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

b = sorted([tuple(map(int,line.split()))[::-1] for line in f])

x = sqrt_tree([bi[2] for bi in b],[min,max])
y = sqrt_tree([bi[1] for bi in b],[min,max])

max_size = i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k][0] + d < b[j][0]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i][0] + d < b[k][0]:
            break
        j = k

    max_size = max(max_size,(x.q(max,i,j) - x.q(min,i,j)) * (y.q(max,i,j) - y.q(min,i,j)))
    j+=1
    
print(max_size)

Submission status: Time Limit Exceeded

Solution code:
import math
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(len(dat) // self.sq)]
    
    #query
    def q(self,l,r):
        r += 1
        if math.ceil(l / self.sq) >= r // self.sq:
            return self.f(self.dat[l:r])
        ret = []
        if math.ceil(l / self.sq) < len(self.baqet):
            ret.append(self.f(self.baqet[math.ceil(l / self.sq):r // self.sq]))
        if l % self.sq:
            ret.append(self.f(self.dat[l:l + self.sq]))
        if r % self.sq:
            ret.append(self.f(self.dat[r - r % self.sq:r]))
        return self.f(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):
        while b[l] + d < b[r]:
            l += 1
        for k in range(r,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: Time Limit Exceeded

Solution code:
import math
class SegmentTree:
    def __init__(self, dat, f, sentinel):
        self.pad = 2 ** math.ceil(math.log(len(dat),2))
        self.dat = [None] * self.pad + dat + [sentinel] * (self.pad - len(dat))
        self.f = f
        self.sentinel = sentinel
        for i in range(self.pad - 1, 0, -1):
            self.dat[i] = self.f(self.dat[i * 2:i * 2 + 2])
        
    def q(self,l,r):
        return self._q(self.pad + l,self.pad + r,1,self.pad,len(self.dat) - 1)
    def _q(self,a,b,k,l,r):
        if b < l or r < a:
            return self.sentinel
        elif a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self._q(a,b,k * 2,l,(l+r)//2)
            vr = self._q(a,b,k * 2 + 1,(l+r)//2 + 1,r)
            return self.f(vl,vr)
        
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 = SegmentTree([max(x[bi]) for bi in b],max,sentinel = -1)
xmin = SegmentTree([min(x[bi]) for bi in b],min,sentinel = 2000001)
ymax = SegmentTree([max(y[bi]) for bi in b],max,sentinel = -1)
ymin = SegmentTree([min(y[bi]) for bi in b],min,sentinel = 2000001)

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
        yield l,r
        l += 1
        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)