Problem:


Score : 400 points

Problem Statement

You are given a sequence A_1, A_2, ..., A_N and an integer K.

Print the maximum possible length of a sequence B that satisfies the following conditions:

B is a (not necessarily continuous) subsequence of A.

For each pair of adjacents elements of B, the absolute difference of the elements is at most K.

Constraints

1 \leq N \leq 300,000

0 \leq A_i \leq 300,000

0 \leq K \leq 300,000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1
A_2
:
A_N

Output

Print the answer.

Sample Input 1

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

Sample Output 1

7

For example, B = (1, 4, 3, 6, 9, 7, 4) satisfies the conditions.

It is a subsequence of A = (1, 5, 4, 3, 8, 6, 9, 7, 2, 4).

All of the absolute differences between two adjacent elements (|1-4|, |4-3|, |3-6|, |6-9|, |9-7|, |7-4|) are at most K = 3.



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


Sample output:
7

Submission status: Runtime Error

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def NLI(n):return [[int(i) for i in input().split()] for i in range(n)]
def NLI_(n):return [[int(i)-1 for i in input().split()] for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def INP():
    N=10;A=10
    n=random.randint(1,N)
    a=[random.randint(1,A) for i in range(n)]
    return n,a
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
#mo=998244353
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()
 
## Segment Tree ##

## Test case: ABC 146 F
## https://atcoder.jp/contests/abc146/tasks/abc146_f

## Initializer Template ##
# Range Sum:        sg=SegTree(n)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

class SegTree:
    def __init__(self,n,init_val=0,function=lambda a,b:a+b,ide=0):
        self.size=n
        self.ide_ele=ide
        self.num=1<<(self.size-1).bit_length()
        self.table=[self.ide_ele]*2*self.num
        self.index=[0]*2*self.num
        self.lazy=[self.ide_ele]*2*self.num
        self.func=function
        #set_val
        if not hasattr(init_val,"__iter__"):
            init_val=[init_val]*self.size
        for i,val in enumerate(init_val):
            self.table[i+self.num-1]=val
            self.index[i+self.num-1]=i
        #build
        for i in range(self.num-2,-1,-1):
            self.table[i]=self.func(self.table[2*i+1],self.table[2*i+2])
            if self.table[i]==self.table[i*2+1]:
                self.index[i]=self.index[i*2+1]
            else:
                self.index[i]=self.index[i*2+2]
        
    def update(self,k,x):
        k+=self.num-1
        self.table[k]=x
        while k:
            k=(k-1)//2
            res=self.func(self.table[k*2+1],self.table[k*2+2])
            self.table[k]=res
            
            ## Remove if index is not needed
            if res==self.table[k*2+1]:
                self.index[k]=self.index[k*2+1]
            else:
                self.index[k]=self.index[k*2+2]
            ## Remove if index is not needed
        
    def evaluate(k,l,r): #遅延評価処理
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1==0:
                res=self.func(res,self.table[p])
            if q&1==1:
                res=self.func(res,self.table[q])
                q-=1
            p=p>>1
            q=(q-1)>>1
        if p==q:
            res=self.func(res,self.table[p])
        else:
            res=self.func(self.func(res,self.table[p]),self.table[q])
        return res
    
    def query_id(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        res=self.ide_ele
        idx=p
        while q-p>1:
            if p&1==0:
                res=self.func(res,self.table[p])
                if res==self.table[p]:
                    idx=self.index[p]
            if q&1==1:
                res=self.func(res,self.table[q])
                if res==self.table[q]:
                    idx=self.index[q]
                q-=1
            p=p>>1
            q=(q-1)>>1
        if p==q:
            res=self.func(res,self.table[p])
            if res==self.table[p]:
                idx=self.index[p]
        else:
            res=self.func(self.func(res,self.table[p]),self.table[q])
            if res==self.table[p]:
                idx=self.index[p]
            elif res==self.table[q]:
                idx=self.index[q]
        return idx


    def __str__(self):
        # 生配列を表示
        rt=self.table[self.num-1:self.num-1+self.size]
        return str(rt)

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]
 
    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
 
show_flg=False
show_flg=True
 
ans=0

n,k=LI()
a=NI(n)

sg=SegTree(n+2,init_val=0,function=max,ide=0)
for i in a:
    l=max(0,i-k)
    r=min(n,i+k)
    sg.update(i,max(sg.table[i],sg.query(l,r+1)+1))

print(sg.query(0,n+1))

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
a=[int(input()) for i in range(n)]

ide_ele = 0

def segfunc(x, y):
    return max(x,y)

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r): #[l, r) 0-index
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

al = [0]*(n+1)
seg = SegTree(al, segfunc, ide_ele)

for num in a:
    l=max(0,num-k)
    r=min(n,num+k+1)
    mx = seg.query(l,r)
    seg.update(num,mx+1)

print(seg.query(0,n))

Submission status: Runtime Error

Solution code:
n, k = map(lambda x: int(x), input().split())

list_a = []
for _ in range(n):
     list_a.append(int(input()))
        
memo = dict()

# i番目以降の要素からなるsublistの長さとして最長のものの長さを返す
def sublist_max_length(current_value, i):
#     if (current_value, i) in memo.keys():
#         return memo[(current_value, i)]
    if i == n-1:
        if (current_value is None) or (abs(current_value - list_a[i]) <= k):
#             memo[(current_value, i)] = 1
#             return memo[(current_value, i)]
            return 1
#         memo[(current_value, i)] = 0
#         return memo[(current_value, i)]
        return 0
    
    if (current_value is None) or (abs(current_value - list_a[i]) <= k):
        # iの値をsublistに含めるor含めない
#         memo[(current_value, i)] = max(1+sublist_max_length(list_a[i], i+1), sublist_max_length(current_value, i+1))
#         return memo[(current_value, i)]
        return max(1+sublist_max_length(list_a[i], i+1), sublist_max_length(current_value, i+1))
#     memo[(current_value, i)] = sublist_max_length(current_value, i+1)
#     return memo[(current_value, i)]
    return sublist_max_length(current_value, i+1)


print(sublist_max_length(None, 0))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve_0_WA(N, K, AS):
    candidates = [[0]]
    for i in range(1, N):
        A = AS[i]
        new_candidates = []
        for c in candidates:
            if abs(AS[c[-1]] - A) <= K:
                new_candidates.append(c[:])
                c.append(i)
                new_candidates.append(c)
                break
            else:
                new_candidates.append(c)
        else:
            new_candidates.append([i])
        candidates = new_candidates
        candidates.sort(key=len, reverse=True)
        debug("candidates", candidates)
    return len(candidates[0])


def set_depth(depth):
    global DEPTH, SEGTREE_SIZE, NONLEAF_SIZE
    DEPTH = depth
    SEGTREE_SIZE = 1 << DEPTH
    NONLEAF_SIZE = 1 << (DEPTH - 1)


def set_width(width):
    global WIDTH
    WIDTH = width
    set_depth((width - 1).bit_length() + 1)


def point_set(table, pos, value, binop):
    pos = pos + NONLEAF_SIZE
    table[pos] = value
    while pos > 1:
        pos >>= 1
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1],
        )


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += SEGTREE_SIZE // 2
    right += SEGTREE_SIZE // 2
    while left < right:
        if left & 1:
            ret_left = binop(ret_left, table[left])
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right)

        left //= 2
        right //= 2
    return binop(ret_left, ret_right)


def bisect_left(table, left, right, value):
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    left_left = None
    right_left = None
    while left < right:
        if left & 1:
            if left_left is None and table[left] >= value:
                left_left = left
            left += 1
        if right & 1:
            if table[right - 1] >= value:
                right_left = right - 1
        left >>= 1
        right >>= 1

    if left_left is not None:
        pos = left_left
        while pos < NONLEAF_SIZE:
            if table[2 * pos] >= value:
                pos = 2 * pos
            else:
                pos = 2 * pos + 1
        return pos - NONLEAF_SIZE
    elif right_left is not None:
        pos = right_left
        while pos < NONLEAF_SIZE:
            if table[2 * pos] >= value:
                pos = 2 * pos
            else:
                pos = 2 * pos + 1
        return pos - NONLEAF_SIZE
    else:
        return WIDTH


def full_up(table, binop):
    for i in range(NONLEAF_SIZE - 1, 0, -1):
        table[i] = binop(
            table[2 * i],
            table[2 * i + 1])


def solve_1(N, K, AS):
    count = [0] * 300_000
    count[AS[0]] = 1
    for i in range(1, N):
        A = AS[i]
        start = max(0, A - K)
        best = max(count[start:A + K + 1])
        count[A] = best + 1
    return max(count)


def solve(N, K, AS):
    set_width(300_010)

    count = [0] * SEGTREE_SIZE
    point_set(count, AS[0], 1, max)
    for i in range(1, N):
        A = AS[i]
        start = max(0, A - K)
        end = A + K + 1

        # best = max(count[start:end])
        best = range_reduce(count, start, end, max, -INF)
        count[A] = best + 1
        point_set(count, A, best + 1, max)
    return range_reduce(count, 0, N, max, -INF)


def main():
    # parse input
    N, K = map(int, input().split())
    AS = []
    for _i in range(N):
        AS.append(int(input()))

    print(solve(N, K, AS))


# tests
T1 = """
10 3
1
5
4
3
8
6
9
7
2
4
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
7
"""

T2 = """
6 2
5
7
3
3
3
3
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
5
"""

T3 = """
6 2
5
7
3
3
3
3
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
5
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Runtime Error

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[0]*n
i=n
while i:i-=1;d[i]=max(d[j]for j in range(i,min(i+99,n))if abs(a[~i]-a[-j])<=k)+1
print(max(d))

Submission status: Runtime Error

Solution code:


class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

n,k = map(int,input().split())
seg = SegTree(400000)
# a = [0]*n
# seg.build(a)
for i in range(n):
    a = int(input())
    seg.set_val(a,seg.fold(a-k,a+k+1) + 1)

print(seg.fold(0,400000))

Submission status: Runtime Error

Solution code:


class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

n,k = map(int,input().split())
seg = SegTree(400000)
a = [0]*n
seg.build(a)
for i in range(n):
    a = int(input())
    seg.set_val(a,seg.fold(a-k,a+k+1) + 1)

print(seg.fold(0,400000))

Submission status: Runtime Error

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

class SegmentTree(object):
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)
 
	# 区間クエリの種類
	def calc(self, a, b):
		return max(a, b)
 
	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])
 
	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
 
		return m

def main():
    n, k = i_map()
    seg = SegmentTree(3 * (10 ** 5) + 2)
    for _ in range(n):
        a = i_input()
		l = max(0, a - k)
        r = min(n - 1, a + k)
        res = seg.query(l, r)
        seg.update(a, res + 1)
 
    print(seg.query(0, n - 1))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
d=[0]*6**8
n,k,*a=map(int,open(0).read().split()+d)
for i in range(n):d[i]=max(d[j]for j in range(i-99,i)if abs(a[i]-a[j])<=k)+1
print(max(d))

Submission status: Runtime Error

Solution code:
d=[0]*6**8
n,k,*a=map(int,open(0).read().split())+d
for i in range(n):d[i]=max(d[j]for j in range(i-99,i+1)if abs(a[i]-a[j])<=k)+1
print(max(d))

Submission status: Runtime Error

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[0]*n
for i in range(n):d[i]=max(d[j]for j in range(i-99,i+1)if abs(a[i]-a[j])<=k)+1
print(max(d))

Submission status: Runtime Error

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[0]*6**8
for i in range(n):d[i]=max(d[j]for j in range(i-99,i+1)if abs(a[i]-a[j])<=k)+1
print(max(d))

Submission status: Runtime Error

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[1]*n
for i in range(n):d[i]=max((d[i],d[j]+1)[abs(a[i]-a[j])<=k]for j in range(max(0,i-99),i))
print(max(d))

Submission status: Runtime Error

Solution code:
# Segment Treeを使う。一点更新，区間最大値

N, K = map(int, input().split())

seglen = 1 << 19

segtree = [0 for _ in range(seglen * 2)]
# segtree[seglen + i] = Bの最後の値に i を使う時のlongest len

def segset(ind, val):
    segtree[ind] = val
    ind //= 2
    while ind != 0:
        segtree[ind] = max(segtree[ind*2], segtree[ind*2 + 1])
        ind //= 2
    return


def segmax(l, r):
    ret = 0

    while l < r:

        if l % 2 == 1:
            ret = max(ret, segtree[l])
            l += 1
        l //= 2

        if r % 2 == 1:
            ret = max(ret, segtree[r - 1])
            r -= 1
        r //= 2

    return ret

A = []
for _ in range(N):
    a = int(input())
    a -= 1
    A.append(a)

ans = 0

for a in A:
    a_ind = seglen + a

    l = max(seglen, a_ind - K)
    r = min(seglen + 4000000, a_ind + K + 1)

    longest = segmax(l, r)

    segset(a_ind, longest + 1)

    ans = max(ans, longest + 1)

print(ans)

Submission status: Runtime Error

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[1]*n
for i in range(n):d[i]=max(d[j]for j in range(max(0,i-99),i)if abs(a[i]-a[j])<=k)+1
print(max(d))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
#Union-Find木
#par[i]:iの親　deep[i]:iの深さ　size[i]:iの大きさ
par=[i for i in range(n)]
deep=[1]*n
size=[1]*n

#親を見つける
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])

#二つのグループを統合する
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1

#xとyが同じグループに属するかどうか
def same(x,y):
  return find(x)==find(y)

#xが属するグループの要素数を返す
def group_count(x):
  return size[find(x)]

#連結成分の個数を返す
def count():
  check=set()
  for i in par:
    parent=find(i)
    if parent not in check:
      check.add(parent)
  return len(check)

for i in range(m):
  a,b=map(int,input().split())
  unite(a,b)
s=count()
print(s-1)

Submission status: Runtime Error

Solution code:
import math
import sys
import os

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")


N,K = LI()
A = [I() for _ in range(N)]
ans = 0

t = [0]*300001

for a in A:
    start = max(0, a - K)
    end = min(N + 1, a + K+1)
    t[a]=max(t[start:end])+1

ans = max(t)

# # ビット全探索
# for i in range(1 << N):
#     c = 0
#     flag = True
#     before = -1
#     for j in range(N):
#         if (i >> j) & 1 == 0:
#             continue
#         if not (before == -1) and abs(before - A[j])>K:
#             flag = False
#             break
#         before = A[j]
#         c += 1
#     # 全てX以上であれば更新
#     if flag:
#         ans = max(ans, c)


print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.buffer.readline

n, k = map(int, input().split())

max_n = 300000 + 10
keta = max_n.bit_length()
num = 1 << (keta - 1)
SEG = [0] * (2 * num)

func = max
ele = 0


def update(idx, val):
    idx += num
    SEG[idx] = val
    for i in reversed(range(1, num)):
        SEG[i] = func(SEG[2 * i], SEG[2 * i + 1])


def query(left, right):
    res_left = ele
    res_right = ele
    left += num
    right += num
    while left < right:
        if left & 1:
            res_left = func(res_left, SEG[left])
            left += 1
        if right & 1:
            right -= 1
            res_right = func(SEG[right], res_right)
        left //= 2
        right //= 2
    return func(res_left, res_right)


ans = 0
for _ in range(n):
    val = int(input())
    lower = val - k
    upper = val + k
    if lower < 0:
        lower = 0
    if upper > num:
        upper = num
    temp = query(lower, upper + 1)
    update(val, temp + 1)
    ans = max(ans, temp + 1)

print(ans)

Submission status: Runtime Error

Solution code:
#####segfunc#####
def segfunc(x, y):
    return max(x, y)
#################
 
#####ide_ele#####
ide_ele = 0
#################
 
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
 
    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1
 
    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele
 
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res
# coding: utf-8
# Your code here!
a = input().split()
N = int(a[0])
M = int(a[1])
a = []
k = [int(input()) for i in range(N)]
 
temp = int(0)
 
for i in range(300001):
    a.append(0)
    
seg = SegTree(a, segfunc, ide_ele)
 
for i in range(N):
    temp = seg.query(max(0, k[i]-M), k[i]+M+1)
    seg.update(k[i], temp+1)
 
print(seg.query(0,300001))

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.buffer.readline

n, k = map(int, input().split())

max_n = 300000 + 10
SEG = [0] * (2 * max_n)

func = max
ele = 0


def update(idx, val):
    idx += max_n
    SEG[idx] = val
    for i in reversed(range(1, max_n)):
        SEG[i] = func(SEG[2 * i], SEG[2 * i + 1])


def query(left, right):
    res_left = ele
    res_right = ele
    left += max_n
    right += max_n
    while left < right:
        if left & 1:
            res_left = func(res_left, SEG[left])
            left += 1
        if right & 1:
            right -= 1
            res_right = func(SEG[right], res_right)
        left //= 2
        right //= 2
    return func(res_left, res_right)


for _ in range(n):
    val = int(input())
    # print("range", max(0, val - k), min(max_n + 1, val + k + 1) - 1)
    lower = val - k
    upper = val + k
    if lower < 0:
        lower = 0
    if upper > max_n:
        upper = max_n
    temp = query(lower, upper + 1)
    update(val, temp + 1)


print(SEG[1])

Submission status: Runtime Error

Solution code:
from typing import Callable, TypeVar, List

T = TypeVar('T')


class SegTree:
    def __init__(self, v: List[T], op: Callable[[T, T], T], e: Callable[[], T]) -> None:
        self.__dict__["_n"] = len(v)
        self.__dict__["log"] = (self.__dict__["_n"] - 1).bit_length()
        self.__dict__["size"] = 1 << self.log
        self.__dict__["d"] = [e() for _ in range(2 * self.size)]
        self.__dict__["op"] = op
        self.__dict__["e"] = e
        for i in range(self.__dict__["_n"]):
            self.__dict__["d"][self.size + i] = v[i]
        for i in reversed(range(1, self.__dict__["size"])):
            self.__dict__["__update__"](i)

    @classmethod
    def init_e(cls, n: int, op: Callable[[T, T], T], e: Callable[[], T]) -> 'SegTree':
        return cls([e() for _ in range(n)], op, e)

    def set(self, p: int, x: T) -> None:
        assert 0 <= p < self._n
        p += self.__dict__["size"]
        self.__dict__["d"][p] = x
        for i in range(1, self.log + 1):
            self.__dict__["__update__"](p >> i)

    def get(self, p: int) -> T:
        assert 0 <= p < self._n
        return self.__dict__["d"][p + self.__dict__["size"]]

    def prod(self, l: int, r: int) -> T:
        assert 0 <= l <= self._n and 0 <= r <= self._n
        sml = self.__dict__["e"]()
        smr = self.__dict__["e"]()
        l += self.__dict__["size"]
        r += self.__dict__["size"]

        while l < r:
            if l & 1:
                sml = self.__dict__["op"](sml, self.__dict__["d"][l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.__dict__["op"](self.__dict__["d"][r], smr)
            l >>= 1
            r >>= 1
        return self.__dict__["op"](sml, smr)

    def all_prod(self) -> T:
        return self.__dict__["d"][1]

    def max_right(self, l: int, f: Callable[[T], bool]):
        assert 0 <= l <= self._n
        assert f(self.e())
        if l == self._n:
            return self._n
        l += self.size
        sm = self.e()
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.op(sm, self.d[l])):
                while l < self.size:
                    l *= 2
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l:
                return self._n

    def min_left(self, r: int, f: Callable[[T], bool]):
        assert 0 <= r <= self._n
        assert f(self.e())
        if r == 0:
            return 0
        r += self.size
        sm = self.e()
        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not f(self.op(self.d[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r:
                return 0

    def __update__(self, k: int) -> None:
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])


n, k = map(int, input().split())
seg = SegTree([0]*400000, max, lambda: 0)
for _ in range(n):
    a = int(input())
    ma = seg.prod(max(0, a-k), min(400000, a+k+1))
    seg.set(a, ma+1)
print(seg.all_prod())