Problem:


天体観測

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

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

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

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

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

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

入力

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

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

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

出力

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

入出力例

入力例

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

 出力例

16 



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


Sample output:
16

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br

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

  make(arr, length, 0)
  return arr

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

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




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

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br

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

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




def main():
  n, d = map(int, input().split())
  stars = []
  blst = []
  for _ in range(n):
    x, y, b = map(int, input().split())
    stars.append((b, x, y))
    blst.append(b)
  blst.sort()
  stars.sort()
  
  length = 1
  while length < n:
    length *= 2
  arr = [None] * (length * 2 - 1)
  for i, star in enumerate(stars):
    x = star[1]
    y = star[2]
    arr[length - 1 + i] = (x, x, y, y, i, i)
  make(arr, length * 2 - 1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br

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

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




def main():
  n, d = map(int, input().split())
  star_dic = {}
  blst = []
  for _ in range(n):
    x, y, b = map(int, input().split())
    if b in star_dic:
      x1, x2, y1, y2 = star_dic[b]
      star_dic[b] = get_min((x1, x2, y1, y2), (x, x, y, y))
    else:
      star_dic[b] = (x, x, y, y)
      blst.append(b)
  stars = sorted(list(star_dic.items()))
  blst.sort()
  blen = len(blst)
  
  length = 1
  while length < blen:
    length *= 2
  arr = [None] * (length * 2 - 1)
  for i, star in enumerate(stars):
    x1, x2, y1, y2 = star[1]
    arr[length - 1 + i] = (x1, x2, y1, y2, i, i)
  make(arr, length * 2 - 1, 0)

  ans = 0
  max_r = 0
  for l in range(blen):
    r = br(blst, blst[l] + d)
    if r == blen or blst[r] != blst[l] + d:
      r -= 1
    if r > max_r:
      a = query(arr, l, r, 0)
      score = (a[1] - a[0]) * (a[3] - a[2])
      if score > ans:
        ans = score
      max_r = r
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br

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

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




def main():
  n, d = map(int, input().split())
  star_dic = {}
  blst = []
  for _ in range(n):
    x, y, b = map(int, input().split())
    if b in star_dic:
      star_dic[b] = get_min(star_dic[b], (x, x, y, y))
    else:
      star_dic[b] = (x, x, y, y)
      blst.append(b)
  stars = sorted(list(star_dic.items()))
  blst.sort()
  blen = len(blst)
  
  length = 1
  while length < blen:
    length *= 2
  arr = [None] * (length * 2 - 1)
  for i, star in enumerate(stars):
    x1, x2, y1, y2 = star[1]
    arr[length - 1 + i] = (x1, x2, y1, y2, i, i)
  make(arr, length * 2 - 1, 0)

  ans = 0
  max_r = 0
  for l in range(blen):
    r = br(blst, blst[l] + d)
    if r == blen or blst[r] != blst[l] + d:
      r -= 1
    if r > max_r:
      x1, x2, y1, y2 = query(arr, l, r, 0)
      score = (x2 - x1) * (y2 - y1)
      if score > ans:
        ans = score
      max_r = r
  print(ans)
main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
f = sys.stdin

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

@memoize
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: Memory Limit Exceeded

Solution code:
from collections import defaultdict
from math import ceil, log2


class SegmentTree:
    left, right = None, None

    def __init__(self, n, bounds, is_min):
        func = min if is_min else max
        sentinel = min_sentinel if is_min else max_sentinel

        n2 = 2 ** ceil(log2(n))
        tree = [sentinel] * (n2 - 1) + bounds + [sentinel] * (n2 - n)
        for i in range(n2 - 2, -1, -1):
            tree[i] = func(tree[i * 2 + 1], tree[i * 2 + 2])
        self.tree = tree
        self.func = func
        self.sentinel = sentinel
        self.create_lr(n2)

    @classmethod
    def create_lr(cls, n2):
        if cls.left and cls.right:
            return
        left = [0] * (n2 - 1) + list(range(n2))
        right = [0] * (n2 - 1) + list(range(n2))
        for i in range(n2 - 2, -1, -1):
            left[i] = left[i * 2 + 1]
            right[i] = right[i * 2 + 2]
        cls.left = left
        cls.right = right

    @classmethod
    def get_indexes(cls, s, t, i=0):
        l, r = cls.left[i], cls.right[i]
        if l >= s and r <= t:
            return {i}
        if l > t or r < s:
            return set()
        return cls.get_indexes(s, t, i * 2 + 1) | cls.get_indexes(s, t, i * 2 + 2)

    def get(self, index_set):
        return self.func(self.tree[i] for i in index_set)


n, d = map(int, input().split())
input_store = defaultdict(lambda: (set(), set()))

while n:
    x, y, b = map(int, input().split())
    x_set, y_set = input_store[b]
    x_set.add(x)
    y_set.add(y)
    n -= 1

min_sentinel, max_sentinel = 2000001, -1

max_b = max(input_store)
list_length = max_b + 1
stars_min_x = [min_sentinel] * (list_length)
stars_min_y = [min_sentinel] * (list_length)
stars_max_x = [max_sentinel] * (list_length)
stars_max_y = [max_sentinel] * (list_length)
for b, xy_set in input_store.items():
    x_set, y_set = xy_set
    stars_min_x[b] = min(x_set)
    stars_min_y[b] = min(y_set)
    stars_max_x[b] = max(x_set)
    stars_max_y[b] = max(y_set)

st_min_x = SegmentTree(list_length, stars_min_x, True)
st_min_y = SegmentTree(list_length, stars_min_y, True)
st_max_x = SegmentTree(list_length, stars_max_x, False)
st_max_y = SegmentTree(list_length, stars_max_y, False)

max_area = 0

for i in input_store:
    if i + d > max_b:
        break
    i_set = SegmentTree.get_indexes(i, i + d)
    current_area = (st_max_x.get(i_set) - st_min_x.get(i_set)) * (st_max_y.get(i_set) - st_min_y.get(i_set))
    if max_area < current_area:
        max_area = current_area

print(max_area)

Submission status: Memory Limit Exceeded

Solution code:
from collections import defaultdict
from math import ceil, log2


class SegmentTree:
    n2 = 0

    def __init__(self, n, bounds, is_min):
        func = min if is_min else max
        sentinel = min_sentinel if is_min else max_sentinel

        n2 = 2 ** ceil(log2(n))
        tree = [sentinel] * (n2 - 1) + bounds + [sentinel] * (n2 - n)
        for i in range(n2 - 2, -1, -1):
            tree[i] = func(tree[i * 2 + 1], tree[i * 2 + 2])
        SegmentTree.n2 = n2
        self.tree = tree
        self.func = func
        self.sentinel = sentinel

    @classmethod
    def get_indexes(cls, s, t):
        n2 = cls.n2
        si, ti = s + n2 - 1, t + n2 - 1
        i_set = set()
        while si < ti:
            if not si & 1:
                i_set.add(si)
                si += 1
            if ti & 1:
                i_set.add(ti)
                ti -= 1
            si = (si - 1) // 2
            ti = (ti - 1) // 2
        if si == ti:
            i_set.add(si)

        return i_set

    def get(self, index_set):
        return self.func(self.tree[i] for i in index_set)


n, d = map(int, input().split())
input_store = defaultdict(lambda: (set(), set()))

while n:
    x, y, b = map(int, input().split())
    x_set, y_set = input_store[b]
    x_set.add(x)
    y_set.add(y)
    n -= 1

min_sentinel, max_sentinel = 2000001, -1

max_b = max(input_store)
list_length = max_b + 1
stars_min_x = [min_sentinel] * (list_length)
stars_min_y = [min_sentinel] * (list_length)
stars_max_x = [max_sentinel] * (list_length)
stars_max_y = [max_sentinel] * (list_length)
for b, xy_set in input_store.items():
    x_set, y_set = xy_set
    stars_min_x[b] = min(x_set)
    stars_min_y[b] = min(y_set)
    stars_max_x[b] = max(x_set)
    stars_max_y[b] = max(y_set)

st_min_x = SegmentTree(list_length, stars_min_x, True)
st_min_y = SegmentTree(list_length, stars_min_y, True)
st_max_x = SegmentTree(list_length, stars_max_x, False)
st_max_y = SegmentTree(list_length, stars_max_y, False)

max_area = 0

for i in input_store:
    if i + d > max_b:
        break

    i_set = SegmentTree.get_indexes(i, i + d)
    min_x = st_min_x.get(i_set)
    if min_x == min_sentinel:
        continue
    current_area = (st_max_x.get(i_set) - min_x) * (st_max_y.get(i_set) - st_min_y.get(i_set))
    if max_area < current_area:
        max_area = current_area

print(max_area)

Submission status: Memory Limit Exceeded

Solution code:
from collections import defaultdict
from math import ceil, log2
import gc


class SegmentTree:
    n2 = 0

    def __init__(self, n, bounds, is_min):
        func = min if is_min else max
        sentinel = min_sentinel if is_min else max_sentinel

        n2 = 2 ** ceil(log2(n))
        tree = [sentinel] * (n2 - 1) + bounds + [sentinel] * (n2 - n)
        for i in range(n2 - 2, -1, -1):
            tree[i] = func(tree[i * 2 + 1], tree[i * 2 + 2])
        SegmentTree.n2 = n2
        self.tree = tree
        self.func = func
        self.sentinel = sentinel

    @classmethod
    def get_indexes(cls, s, t):
        n2 = cls.n2
        si, ti = s + n2 - 1, t + n2 - 1
        i_set = set()
        while si < ti:
            if not si & 1:
                i_set.add(si)
                si += 1
            if ti & 1:
                i_set.add(ti)
                ti -= 1
            si = (si - 1) // 2
            ti = (ti - 1) // 2
        if si == ti:
            i_set.add(si)

        return i_set

    def get(self, index_set):
        return self.func(self.tree[i] for i in index_set)


n, d = map(int, input().split())
input_store = defaultdict(lambda: (set(), set()))

while n:
    x, y, b = map(int, input().split())
    x_set, y_set = input_store[b]
    x_set.add(x)
    y_set.add(y)
    n -= 1

min_sentinel, max_sentinel = 2000001, -1

max_b = max(input_store)
list_length = max_b + 1
stars_min_x = [min_sentinel] * (list_length)
stars_min_y = [min_sentinel] * (list_length)
stars_max_x = [max_sentinel] * (list_length)
stars_max_y = [max_sentinel] * (list_length)
for b, xy_set in input_store.items():
    x_set, y_set = xy_set
    stars_min_x[b] = min(x_set)
    stars_min_y[b] = min(y_set)
    stars_max_x[b] = max(x_set)
    stars_max_y[b] = max(y_set)

st_min_x = SegmentTree(list_length, stars_min_x, True)
del stars_min_x
st_min_y = SegmentTree(list_length, stars_min_y, True)
del stars_min_y
st_max_x = SegmentTree(list_length, stars_max_x, False)
del stars_max_x
st_max_y = SegmentTree(list_length, stars_max_y, False)
del stars_max_y
gc.collect()

max_area = 0

for i in input_store:
    if i + d > max_b:
        break

    i_set = SegmentTree.get_indexes(i, i + d)
    min_x = st_min_x.get(i_set)
    if min_x == min_sentinel:
        continue
    current_area = (st_max_x.get(i_set) - min_x) * (st_max_y.get(i_set) - st_min_y.get(i_set))
    if max_area < current_area:
        max_area = current_area

print(max_area)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

N, d = map(int, sys.stdin.readline().split())
a = sorted([(b, x, y) for l in sys.stdin.readlines() for x, y, b in (map(int, l.split()),)])
x_max, x_min, y_max, y_min = [], [], [], []

ans = 0
for b, x, y in a:
    heappush(x_max, (-x, b))
    heappush(x_min, (x, b))
    heappush(y_max, (-y, b))
    heappush(y_min, (y, b))
    for _a in (x_max, x_min, y_max, y_min):
        while _a[0][1] < b-d:
            heappop(_a)

    ans = max(ans, (-x_max[0][0]-x_min[0][0])*(-y_max[0][0]-y_min[0][0]))
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter

N, d = map(int, sys.stdin.readline().split())
x_max, x_min, y_max, y_min = [], [], [], []

ans = 0
for x, y, b in sorted([list(map(int, l.split())) for l in sys.stdin.readlines()], key=itemgetter(2)):
    heappush(x_max, (-x, b))
    heappush(x_min, (x, b))
    heappush(y_max, (-y, b))
    heappush(y_min, (y, b))
    for _a in (x_max, x_min, y_max, y_min):
        while _a[0][1] < b-d:
            heappop(_a)

    area = (-x_max[0][0]-x_min[0][0])*(-y_max[0][0]-y_min[0][0])
    if area > ans:
        ans = area
print(ans)

Submission status: Accepted

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],dat[i * 2 + 1])
        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)


pad = len(xmax) // 2
max_size = 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):
    l += pad 
    r += pad
    index = create_index(l,r)

    now_xmax = max(xmax[i] for i in index)
    now_ymax = max(ymax[i] for i in index)
    if max_size < now_xmax * now_ymax:
        max_size = max(max_size,((now_xmax - min(xmin[i] for i in index)) * (now_ymax - min(ymin[i] for i in index))))
print(max_size)

Submission status: Accepted

Solution code:
n,d = map(int,input().split())
star = []
for i in range(n):
    x,y,b = map(int,input().split())
    star.append((b,x,y))
star.sort()

INF = 10**9
q1 = []
q2 = []
minmax1 = [(INF,INF,-INF,-INF)]
minmax2 = [(INF,INF,-INF,-INF)]
r = 0
ans = 0

def add(que, dat):
    xmin, ymin, xmax, ymax = que[-1]
    x, y = dat
    if x < xmin:
        xmin = x
    if x > xmax:
        xmax = x
    if y < ymin:
        ymin = y
    if y > ymax:
        ymax = y
    que.append((xmin, ymin, xmax, ymax))

for s in star:
    while r < n and star[r][0]-s[0] <= d:
        br, xr, yr = star[r]
        xy = (xr,yr)
        q2.append(xy)
        add(minmax2,xy)
        r += 1
    xmin = min(minmax1[-1][0], minmax2[-1][0])
    ymin = min(minmax1[-1][1], minmax2[-1][1])
    xmax = max(minmax1[-1][2], minmax2[-1][2])
    ymax = max(minmax1[-1][3], minmax2[-1][3])
    area = (xmax-xmin)*(ymax-ymin)
    if area > ans:
        ans = area
    if len(q1) == 0:
        while len(q2) > 0:
            xy = q2.pop()
            minmax2.pop()
            q1.append(xy)
            add(minmax1, xy)
    q1.pop()
    minmax1.pop()

print(ans)

Submission status: Accepted

Solution code:
import operator
from collections import deque
N, d = map(int, input().split())
P = [list(map(int, input().split())) for i in range(N)]
P.sort(key=operator.itemgetter(2))
xd_min = deque()
xd_max = deque()
yd_min = deque()
yd_max = deque()
s = -1; t = 0
ans = 0
while t < N:
    t0 = t
    while t < N-1 and P[t][2] == P[t+1][2]:
        t += 1
    b = P[t][2]
    while b - P[s+1][2] > d:
        s += 1

    while xd_min and xd_min[0][0] <= s:
        xd_min.popleft()
    while xd_max and xd_max[0][0] <= s:
        xd_max.popleft()
    while yd_min and yd_min[0][0] <= s:
        yd_min.popleft()
    while yd_max and yd_max[0][0] <= s:
        yd_max.popleft()

    for i in range(t0, t+1):
        x, y, b = P[i]
        while xd_min and x <= xd_min[-1][1]:
            xd_min.pop()
        xd_min.append((i, x))
        while xd_max and xd_max[-1][1] <= x:
            xd_max.pop()
        xd_max.append((i, x))
        while yd_min and y <= yd_min[-1][1]:
            yd_min.pop()
        yd_min.append((i, y))
        while yd_max and yd_max[-1][1] <= y:
            yd_max.pop()
        yd_max.append((i, y))

    r = (xd_max[0][1] - xd_min[0][1]) * (yd_max[0][1] - yd_min[0][1])
    ans = max(ans, r)

    t += 1
print(ans)

Submission status: Runtime Error

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

ans = max(ans, score(keys_to_ind[keys[kl]], keys_to_ind[keys[kr]]))
print(ans)

Submission status: Runtime Error

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 kr < end:
  ans = max(ans, score(kl, 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(kl, kr))
print(ans)