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:
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.f(self.dat[i] for i in self.get_index(l,r))
        
    def get_index(self,l,r):
        l += self.pad 
        r += self.pad + 1
        while l < r:
            if r & 1:
                r -= 1
                yield r
            if l & 1:
                yield l
                l += 1
            l >>= 1
            r >>= 1
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)

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.f(self.dat[i] for i in self.get_index(l,r))
    #[l,r)
    def get_index(self,l,r):
        l += self.pad 
        r += self.pad
        while l < r:
            if r & 1:
                r -= 1
                yield r
            if l & 1:
                yield l
                l += 1
            l >>= 1
            r >>= 1
    def q2(self,index):
        return self.f(self.dat[i] for i in index)

    def get_index2(self,l,r):
        l += self.pad 
        r += self.pad
        ret = []
        while l < r:
            if r & 1:
                r -= 1
                ret.append(r)
            if l & 1:
                ret.append(l)
                l += 1
            l >>= 1
            r >>= 1
        return ret
import sys
f = sys.stdin

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

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

b = sorted(x.keys())

xmax = 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
        r += 1
        yield l,r
        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))
size = []
for l,r in get_lr(b,d):
    index = xmax.get_index2(l,r)
    size.append((xmax.q2(index) - xmin.q2(index)) * (ymax.q2(index) - ymin.q2(index)))
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,index):
        return self.f(self.dat[i] for i in index)

    def get_index(self,l,r):
        l += self.pad 
        r += self.pad
        ret = []
        while l < r:
            if r & 1:
                r -= 1
                ret.append(r)
            if l & 1:
                ret.append(l)
                l += 1
            l >>= 1
            r >>= 1
        return ret
import sys
f = sys.stdin

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

x,y = {},{}
for line in f:
    xi, yi, bi = map(int, line.split())
    if bi not in x:
#        x[bi],y[bi] = [],[]
#    x[bi].append(xi)
#    y[bi].append(yi)
        x[bi],y[bi] = set(),set()
    x[bi].update([xi])
    y[bi].update([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
        r += 1
        yield l,r
        l += 1
    
size = []
for l,r in get_lr(b,d):
    index = xmax.get_index(l,r)
    size.append((xmax.q(index) - xmin.q(index)) * (ymax.q(index) - ymin.q(index)))
print(max(size))

Submission status: Time Limit Exceeded

Solution code:
import math
def segmentTree(dat, f, sentinel):
        pad = 2 ** math.ceil(math.log(len(dat),2))
        dat = [None] * 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

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
        r += 1
        yield l,r
        l += 1
    
size = []
pad = len(xmax) // 2
for l,r in get_lr(b,d):
    # 参照するsegmentのindexを生成　※速度のためインライン展開
    l += pad 
    r += pad
    index = []
    while l < r:
        if r & 1:
            r -= 1
            index.append(r)
        if l & 1:
            index.append(l)
            l += 1
        l >>= 1
        r >>= 1

    size.append((max(xmax[i] for i in index)
                 - min(xmin[i] for i in index))
                * (max(ymax[i] for i in index)
                   - min(ymin[i] for i in index)))
print(max(size))

Submission status: Time Limit Exceeded

Solution code:
import math
def segmentTree(dat, f, sentinel):
        pad = 2 ** math.ceil(math.log(len(dat),2))
        dat = [None] * 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
import sys
f = sys.stdin

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

x,y = {},{}
for line in f:
    xi, yi, bi = map(int, line.split())
    try:#if key not in dict よりtry exceptの方が早い
        x[bi].append(xi)
        y[bi].append(yi)
    except KeyError:
        x[bi],y[bi] = [xi],[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
        r += 1
        yield l,r
        l += 1

size = []
sa = size.append #万単位で呼び出す場合は若干早くなる
pad = len(xmax) // 2
for l,r in get_lr(b,d):
    # 参照するsegmentのindexを生成　※速度のためインライン展開
    l += pad 
    r += pad
    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

    sa((max(xmax[i] for i in index)
                 - min(xmin[i] for i in index))
                * (max(ymax[i] for i in index)
                   - min(ymin[i] for i in index)))
print(max(size))

Submission status: Time Limit Exceeded

Solution code:
import math
import array
def segmentTree(dat, f, sentinel):
        pad = 2 ** math.ceil(math.log(len(dat),2))
        dat = array.array('L',[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

import sys
f = sys.stdin


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

x,y = {},{}
for line in f:
    xi, yi, bi = map(int, line.split())
    try:#if key not in dict よりtry exceptの方が早い
        x[bi].append(xi)
        y[bi].append(yi)
    except KeyError:
        x[bi],y[bi] = [xi],[yi]

b = sorted(x.keys())

xmax = segmentTree([max(x[bi]) for bi in b],max,sentinel = 0)
xmin = segmentTree([min(x[bi]) for bi in b],min,sentinel = 2000000)
ymax = segmentTree([max(y[bi]) for bi in b],max,sentinel = 0)
ymin = segmentTree([min(y[bi]) for bi in b],min,sentinel = 2000000)

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
    
size = []
sa = size.append #万単位で呼び出す場合は若干早くなる
pad = len(xmax) // 2
for l,r in get_lr(b,d):
    # 参照するsegmentのindexを生成　※速度のためインライン展開
    l += pad 
    r += pad
    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

    sa((max(xmax[i] for i in index)
                 - min(xmin[i] for i in index))
                * (max(ymax[i] for i in index)
                   - min(ymin[i] for i in index)))
print(max(size))

Submission status: Time Limit Exceeded

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
for l,r in get_lr(b,d):
    # 参照するsegmentのindexを生成　※速度のためインライン展開
    l += pad 
    r += pad
    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

    sa((max(xmax[i] for i in index)
                 - min(xmin[i] for i in index))
                * (max(ymax[i] for i in index)
                   - min(ymin[i] for i in index)))
print(max(size))

Submission status: Time Limit Exceeded

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

        sa((now_xmax - now_xmin) * (now_ymax - now_ymin))
    pre_xmax,pre_xmin,pre_ymax,pre_ymin=now_xmax,now_xmin,now_ymax,now_ymin
    m = r
print(max(size))

Submission status: Time Limit Exceeded

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()))
scale = []
for j in range(len(a)):
    minlight = a[j][2]
    astars = []
    for k in range(len(a)):
        if (a[k][2] >= minlight and a[k][2] <= minlight + lightrange):
            astars.append(a[k])
    astarsx = [astars[l][0] for l in range(len(astars))]
    astarsy = [astars[m][1] for m in range(len(astars))]
    p = max(astarsx)
    q = min(astarsx)
    r = max(astarsy)
    s = min(astarsy)
    scale.append((p-q)*(r-s))
print max(scale)

Submission status: Time Limit Exceeded

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)):
        if (a[k][2] >= minlight and a[k][2] <= minlight + lightrange):
            astars.append(a[k])
    astarsx = [astars[l][0] for l in range(len(astars))]
    astarsy = [astars[m][1] for m in range(len(astars))]
    p = max(astarsx)
    q = min(astarsx)
    r = max(astarsy)
    s = min(astarsy)
    pqrs = (p - q) * (r - s)
    if (pqrs > scale):
        scale = pqrs
    del a[0]
    if len(a) < 4:
        break;

print scale

Submission status: Time Limit Exceeded

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)):
        if (a[k][2] >= minlight and a[k][2] <= minlight + lightrange):
            astars.append(a[k])
    #astarsx = [astars[l][0] for l in range(len(astars))]
    #astarsy = [astars[m][1] for m in range(len(astars))]
    length = len(astars)
    #print astars
    astars.sort(key=lambda x:x[0])
    #p = max(astarsx)
    #q = min(astarsx)
    #r = max(astarsy)
    #s = min(astarsy)
    p = astars[length-1][0]
    q = astars[0][0]
    astars.sort(key=lambda x:x[1])
    r = astars[length-1][1]
    s = astars[0][1]
    pqrs = (p - q) * (r - s)
    if (pqrs > scale):
        scale = pqrs
    del a[0]
    if len(a) < 4:
        break;

print scale

Submission status: Time Limit Exceeded

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][1]>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: Time Limit Exceeded

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):
            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]
    if len(a) < 2:
        break;

print scale

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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):
    k=0
    x=[]
    y=[]
    while(a[k][2]<=a[0][2] + lightrange):
        x.append(a[k][0])
        y.append(a[k][1])
        k+=1
        if(k==len(a)):
            break
    area = (max(x)-min(x))*(max(y)-min(y))
    scale = max(scale,area)
    del a[0]
print scale

Submission status: Time Limit Exceeded

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):
    k=0
    x=[]
    y=[]
    while(a[k][2]<=a[0][2] + lightrange):
        x.append(a[k][0])
        y.append(a[k][1])
        k+=1
        if(k==len(a)):
            break
    scale.append((max(x)-min(x))*(max(y)-min(y)))
    del a[0]
print max(scale)

Submission status: Time Limit Exceeded

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]
minlight = -1
while(len(a)>1):
    if a[0] == minlight:
        del a[0]
    else :
        k=0
        x=[]
        y=[]
        while(a[k][2]<=a[0][2] + lightrange):
            x.append(a[k][0])
            y.append(a[k][1])
            k+=1
            if(k==len(a)):
                break
        scale.append((max(x)-min(x))*(max(y)-min(y)))
        minlight = a[0][2]
        del a[0]
print max(scale)

Submission status: Time Limit Exceeded

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 z:(z[2],z[0]))
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=[]
Y=[]
k=0
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, (max(X)-min(X))*(max(Y)-min(Y)))
print scale

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, d = map(int, input().split())
ud, od = d // 2, (d + 1) // 2
stars = defaultdict(set)

for _ in range(n):
    x, y, b = map(int, input().split())
    stars[b].add((x, y))

keys = set(stars.keys())
min_b, max_b = min(keys) + ud, max(keys) - od
max_stella = 0

for b in keys.intersection(range(min_b, max_b + 1)):
    max_x, min_x, max_y, min_y = 0, 200001, 0, 200001
    for bb in keys.intersection(range(b - ud, b + od + 1)):
        for xy in stars[bb]:
            (x, y) = xy
            if max_x < x: max_x = x
            if min_x > x: min_x = x
            if max_y < y: max_y = y
            if min_y > y: min_y = y
    stella = (max_x - min_x) * (max_y - min_y)
    if max_stella < stella: max_stella = stella

print(max_stella)

Submission status: Time Limit Exceeded

Solution code:
n, d = map(int, input().split())
ud, od = d // 2, (d + 1) // 2
stars = dict()

for _ in range(n):
    x, y, b = map(int, input().split())
    xys = stars.setdefault(b, [x, x, y, y])
    if xys[0] < x: xys[0] = x
    if xys[1] > x: xys[1] = x
    if xys[2] < y: xys[2] = y
    if xys[3] > y: xys[3] = y

keys = set(stars.keys())
min_b, max_b = min(keys) + ud, max(keys) - od
max_stella = 0

for b in range(min_b, max_b + 1):
    bbs = keys.intersection(range(b - ud, b + od + 1))
    if not bbs: continue
    max_x, min_x, max_y, min_y = 0, 200001, 0, 200001
    for bb in bbs:
        xys = stars[bb]
        if max_x < xys[0]: max_x = xys[0]
        if min_x > xys[1]: min_x = xys[1]
        if max_y < xys[2]: max_y = xys[2]
        if min_y > xys[3]: min_y = xys[3]
    else:
        stella = (max_x - min_x) * (max_y - min_y)
        if max_stella < stella: max_stella = stella

print(max_stella)

Submission status: Time Limit Exceeded

Solution code:
n, d = map(int, input().split())
ud, od = d // 2, (d + 1) // 2
stars = dict()

for _ in range(n):
    x, y, b = map(int, input().split())
    xys = stars.setdefault(b, [x, x, y, y])
    if xys[0] < x: xys[0] = x
    if xys[1] > x: xys[1] = x
    if xys[2] < y: xys[2] = y
    if xys[3] > y: xys[3] = y

keys = set(stars.keys())
min_b, max_b = min(keys) + ud, max(keys) - od
max_stella = 0

for b in range(min_b, max_b + 1):
    bbs = keys.intersection(range(b - ud, b + od + 1))
    if not bbs: continue
    max_x, min_x, max_y, min_y = 0, 200001, 0, 200001
    for bb in bbs:
        (ax, ix, ay, iy) = stars[bb]
        if max_x < ax: max_x = ax
        if min_x > ix: min_x = ix
        if max_y < ay: max_y = ay
        if min_y > iy: min_y = iy
    else:
        stella = (max_x - min_x) * (max_y - min_y)
        if max_stella < stella: max_stella = stella

print(max_stella)

Submission status: Time Limit Exceeded

Solution code:
n, d = map(int, input().split())
ud, od = d // 2, (d + 1) // 2
stars = dict()

for _ in range(n):
    x, y, b = map(int, input().split())
    xys = stars.setdefault(b, [x, x, y, y])
    if xys[0] < x: xys[0] = x
    if xys[1] > x: xys[1] = x
    if xys[2] < y: xys[2] = y
    if xys[3] > y: xys[3] = y

keys = set(stars.keys())
min_b, max_b = min(keys) + ud, max(keys) - od
max_stella = 0

for b in range(min_b, max_b + 1):
    if b + od not in stars: continue
    bbs = keys.intersection(range(b - ud, b + od + 1))
    if not bbs: continue
    max_x, min_x, max_y, min_y = 0, 200001, 0, 200001
    for bb in bbs:
        (ax, ix, ay, iy) = stars[bb]
        if max_x < ax: max_x = ax
        if min_x > ix: min_x = ix
        if max_y < ay: max_y = ay
        if min_y > iy: min_y = iy
    else:
        stella = (max_x - min_x) * (max_y - min_y)
        if max_stella < stella: max_stella = stella

print(max_stella)

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

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).area() for i in range(max_b - d + 1)))