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

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

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

n,k = inpm()
A = inplm(n)

seg = SegTree([0]*300001, segfunc, ide_ele)

for a in A:
    seg.update(a-1,seg.query(max(0,a-k-1),min(300001,a+k)) + 1)

print(seg.query(0,300001))

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

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

n,k = inpm()
A = inplm(n)

seg = SegTree([0]*300001, segfunc, ide_ele)

for a in A:
    seg.update(a-1,seg.query(max(0,a-k-1),min(300001,a+k)) + 1)

print(seg.query(0,n))

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

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

n,k = inpm()
A = inplm(n)

seg = SegTree([0]*300001, segfunc, ide_ele)

for a in A:
    seg.update(a-1,seg.query(max(0,a-k-1),min(n,a+k)) + 1)

print(seg.query(0,n))

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

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

n,k = inpm()
A = inplm(n)

seg = SegTree([0]*300001, segfunc, ide_ele)

for a in A:
    seg.update(a-1,seg.query(max(0,a-k-1),min(n,a+k)) + 1)

print(seg.query(0,n-1))

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

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

n,k = inpm()
A = inplm(n)

seg = SegTree([0]*300000, segfunc, ide_ele)

for a in A:
    seg.update(a-1,seg.query(max(0,a-k-1),min(n,a+k)) + 1)

print(seg.query(0,n-1))

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

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

n,k = inpm()
A = inplm(n)

seg = SegTree([0]*300000, segfunc, ide_ele)

for a in A:
    seg.update(a-1,seg.query(max(0,a-k-1),min(n,a+k)) + 1)

print(seg.query(0,n-1))

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
from collections import deque, defaultdict, Counter
import heapq

# SegTreeの関数
def segfunc(x, y):
    return max(x, y)
#区間の最小値、最大値を求めたい、区間の和を求めたいなど。segfuncに関数を書き込んでください。


# 単位元
# min->inf, max->-inf, add->0, mul->1
ide_ele = - float('inf')


# セグメント木
class SegTree:
    """
    init(init_val, segfunc, ide_ele): 配列init_valで初期化、構築
    update(k, x): k番目の値をxに更新
    query(l, r): 区間[l, r)をsegfuncしたものを返す
    """

    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番目の値をxに更新
        :param k: index(0-index)
        :param 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したものを得る
        :param l: 0-index
        :param r: 0-index
        :return:
        """
        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
def main():
    N, K = MI()
    A = [0] * (3 * 10 ** 5 + 1)
    seg = SegTree(A, segfunc, ide_ele)
    for i in range(N):
        a = I()
        b = seg.query(a - 3, a + 4)
        seg.update(a, b + 1)
    print(seg.query(1, 3 * 10 ** 5 + 1))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b - 1)

        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300000)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, N))

Submission status: Wrong Answer

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

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b - 1)

        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300000)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, N) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, N))

Submission status: Wrong Answer

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

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b - 1)

        while l < r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300005)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, 300005))

Submission status: Wrong Answer

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

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + b

        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300005)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, 300005))

Submission status: Wrong Answer

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

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def query(self, l, r):
        L = l + self.n - 1
        R = r + self.n - 1
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = segfunc(s, self.node[R - 1])
            if L & 1:
                s = segfunc(s, self.node[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300005)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, 300005))

Submission status: Wrong Answer

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

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def query(self, l, r):
        L = l + self.n - 1
        R = r + self.n - 1
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = segfunc(s, self.node[R - 1])
            if L & 1:
                s = segfunc(s, self.node[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300005)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1)
    seg.update(a, tmp)
print(seg.query(0, 300005))

Submission status: Wrong Answer

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

def init(tmpn):
    global noden
    n = 1
    while tmpn > n:
        n *= 2
    noden = n

def update(i, x):
    i += noden-1
    node[i] = x
    while i:
        i = (i-1)//2
        node[i] = segfunc(node[i*2+1], node[i*2+2])

def query(l, r):
    L = l + noden
    R = r + noden
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = segfunc(s, node[R - 1])
        if L & 1:
            s = segfunc(s, node[L - 1])
            L += 1
        L >>= 1
        R >>= 1
    return s

N, K = map(int, input().split())
MAX_N = 2**(300005).bit_length()
a = [int(input()) for _ in range(N)]
node = [0] * (2 * MAX_N)
noden = 0
INF = 0
init(N)
ma = 300005
ans = 0
for i in a:
    tmp = query(max(i - K, 0), min(ma, i + K) + 1)
    update(i, tmp + 1)
    ans = max(ans, tmp + 1)
print(ans)

Submission status: Wrong Answer

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

def init(tmpn):
    global noden
    n = 1
    while tmpn > n:
        n *= 2
    noden = n

def update(i, x):
    i += noden-1
    node[i] = x
    while i:
        i = (i-1)//2
        node[i] = segfunc(node[i*2+1], node[i*2+2])

def query(l, r):
    L = l + noden
    R = r + noden
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = segfunc(s, node[R - 1])
        if L & 1:
            s = segfunc(s, node[L - 1])
            L += 1
        L >>= 1
        R >>= 1
    return s

N, K = map(int, input().split())
MAX_N = 2**(300005).bit_length()
a = [int(input()) for _ in range(N)]
node = [0] * (2 * MAX_N)
noden = 0
INF = 0
init(N)
ma = max(a)
ans = 0
for i in a:
    tmp = query(max(i - K, 0), min(ma, i + K) + 1)
    update(i, tmp + 1)
    ans = max(ans, tmp + 1)
print(ans)

Submission status: Wrong Answer

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

def init(tmpn):
    global noden
    n = 1
    while tmpn > n:
        n *= 2
    noden = n

def update(i, x):
    i += noden-1
    node[i] = x
    while i:
        i = (i-1)//2
        node[i] = segfunc(node[i*2 + 1], node[i*2 + 2])

def query(l, r):
    L = l + noden
    R = r + noden
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = segfunc(s, node[R - 1])
        if L & 1:
            s = segfunc(s, node[L - 1])
            L += 1
        L >>= 1
        R >>= 1
    return s

N, K = map(int, input().split())
MAX_N = 2**(N-1).bit_length()
a = [int(input()) for _ in range(N)]
node = [0] * (2 * 10 ** 6)
noden = 0
INF = 0
init(N)
ma = 30005
ans = 0
for i in a:
    tmp = query(max(i - K, 0), min(ma, i + K + 1))
    update(i, tmp + 1)
    ans = max(ans, tmp + 1)
print(ans)