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:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def getOverlap(a, b):
    return max(0, min(a[1], b[1]) - max(a[0], b[0]) + 1)

def connected_components(n, graph):
    components, visited = [], [False] * n

    def dfs(start):
        component, stack = [], [start]

        while stack:
            start = stack[-1]

            if visited[start]:
                stack.pop()
                continue
            else:
                visited[start] = True
                component.append(start)

            for i in graph[start]:
                if not visited[i]:
                    stack.append(i)

        return component

    for i in range(n):
        if not visited[i]:
            components.append(dfs(i))

    return components

from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1


for _ in range(int(input()) if not True else 1):
    #n = int(input())
    n, k = map(int, input().split())
    a = []
    for i in range(n):
        a += [int(input())]
    st = SegmentTree([0]*400000, func=max)
    dp = [0]*n
    dp[0] = 1
    st.update(a[0], dp[i])
    for i in range(1, n):
        dp[i] = 1 + st.query(max(0,a[i]-k), min(n-1,a[i]+k))
        st.update(a[i], dp[i])
    print(dp[-1])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
ans = 0
a = [int(input()) for i in range(n)]
for i in range(n-1):
    if abs(a[i] - a[i+1]) <= k:
        ans += 1
    else:
        a[i+1] = a[i]
print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]

def seg_function(x,y): # Segment treeで扱うfunction
    return max(x,y)

seg_el=1<<((300000).bit_length()) # Segment treeの台の要素数
SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def update(n,x,seg_el): # A[n]をxに更新
    i=n+seg_el
    SEG[i]=max(SEG[i],x)
    i>>=1 # 子ノードへ
    
    while i!=0:
        SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r): # 区間[l,r)に関するseg_functionを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=0

    while L<R:
        if L & 1:
            ANS=seg_function(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=seg_function(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

for a in A:
    MAX=getvalues(max(0,a-K),min(300000,a+K+1))
    update(a,MAX+1,seg_el)
print(SEG[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

def main():
    N, K = MI()
    B = []
    for i in range(N):
        a = I()
        if i == 0:
            now = a
            B.append(now)
        else:
            if abs(a - now) <= K:
                B.append(a)
                now = a
    print(len(B))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l) 

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
M=max(A)
bit=BIT(M+1)
ans=0

for i in range(N):
    bit.add(A[i],1)
for R in range(M+1):
    l=max(0,R-K)
    res=bit.cum(l,R+1)
    ans=max(ans,res)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]
maxa=max(a)
dp=[0]*(maxa+1)
for x in a:
  tmp=0
  for i in range(3):
    if 0<=x-i-1:tmp=max(tmp,dp[x-i-1])
    if x+i+1<=maxa:tmp=max(tmp,dp[x+i+1])
  dp[x]=tmp+1
print(max(dp))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=[0]*N
    for i in range(N):
        A[i]=int(sys.stdin.readline())

    dp=[0]*(N+1)
    dp[0]=1
    if abs(A[0]-A[1])<=K:
        dp[1]=2
    else:
        dp[1]=1
    
    for i in range(2,N):
        mx=1
        if abs(A[i-2]-A[i])<=K:
            mx=max(mx,dp[i-2]+1)
        if abs(A[i-1]-A[i])<=K:
            mx=max(mx,dp[i-1]+1)
        dp[i]=mx

    print(max(dp))

main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
class SegmentTree:
    def __init__(self,n,segfunc,ide_ele):
        self.segfunc=segfunc
        self.ide_ele=ide_ele
        self.num=2**(n-1).bit_length()
        self.dat=[ide_ele]*2*self.num
    
    def init(self,iter):
        for i in range(len(iter)):
            self.dat[i+self.num]=iter[i]
        for i in range(self.num-1,0,-1):
            self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
    
    def update(self,k,x):
        k+=self.num
        self.dat[k]=x
        while k:
            k//=2
            self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num
        q+=self.num-1
        res=self.ide_ele
        while q-p>1:
            if p&1==1:
                res=self.segfunc(res,self.dat[p])
            if q&1==0:
                res=self.segfunc(res,self.dat[q])
                q-=1
            p=(p+1)//2
            q=q//2
        if p==q:
            res=self.segfunc(res,self.dat[p])
        else:
            res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
        return res

s=SegmentTree(max(A)+1,lambda a,b: max(a,b),0)

s.update(A[0],1)
ans=1

for x in A[1:]:
    p=max(x-K,0)
    q=min(x+K+1,N)
    res=s.query(p,q)
    s.update(x,res+1)
    ans=max(ans,res+1)
print(ans)

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l) 

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
M=max(A)
bit=BIT(M+1)
ans=0

for i in range(N):
    l=max(0,A[i]-K)
    r=min(A[i]+K,M)
    ans=max(ans,bit.cum(l,r+1))
    bit.add(A[i],1)
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class SegmentTree:
        def __init__(self, A, initialize=True, segfunc=max, ident=-2000000000):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)

        def update(self, i, x):
            i += self.N0 - 1
            self.data[i] = x
            for _ in range(self.LV):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            ret_l = self.ident
            ret_r = self.ident
            while l < r:
                if l & 1:
                    ret_l = self.segfunc(ret_l, self.data[l])
                    l += 1
                if r & 1:
                    ret_r = self.segfunc(self.data[r - 1], ret_r)
                    r -= 1
                l >>= 1
                r >>= 1
            return self.segfunc(ret_l, ret_r)

        # return smallest i(l <= i < r) s.t. check(A[i]) == True
        def binsearch(self, l, r, check):
            if not check(self.query(l, r)):
                return r
            l += self.N0 - 1
            val = self.ident
            while True:
                if check(self.segfunc(val, self.data[l])):
                    break
                if l & 1:
                    val = self.segfunc(val, self.data[l])
                    l += 1
                l >>= 1
            while l < self.N0:
                newval = self.segfunc(val, self.data[l * 2])
                if not check(newval):
                    val = newval
                    l = (l << 1) + 1
                else:
                    l <<= 1
            return l - self.N0 + 1

    N, K = map(int, input().split())
    ST = SegmentTree([0] * 300001)
    for _ in range(N):
        a = int(input())
        ST.update(a + 1, ST.query(max(1, a - K + 1), min(300000, a + K + 2)) + 1)
    print(ST.data[1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
now = a.pop(0)
counter = 1
for i in a:
    if abs(now-i) <= k:
        counter += 1
        now = i
print(counter)

Submission status: Time Limit Exceeded

Solution code:
from typing import List, Any
import math
import sys
input = sys.stdin.readline

class SegmentTree:
    
    def __init__(self, array):
        self.n = len(array)
        self.array = [0 for _ in array]+array
        for i in range(self.n-1, 0, -1):
            self.array[i] = max(self.array[i<<1], self.array[i<<1|1])

    def set(self, i, v):
        p = self.n+i
        self.array[p] = v
        while p > 1:
            p >>= 1
            self.array[p] = max(self.array[p<<1], self.array[p<<1|1])

    def max(self, l, r):
        l += self.n
        r += self.n
        answer = 0
        while l < r:
            if l&1:
                answer = max(answer, self.array[l])
                l += 1
            if r&1:
                r -= 1
                answer = max(answer, self.array[r])
            l >>= 1
            r >>= 1
        return answer


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, K = read_ints()
    A = [read_int() for _ in range(N)]
    maxA = max(A)
    segment_tree = SegmentTree([0]*(maxA+1))
    for a in A:
        count = segment_tree.max(max(0, a-K), min(maxA, a+K)+1)
        segment_tree.set(a, count+1)
    return segment_tree.max(0, maxA+1)


if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
# 04 Flat subsequence
#
# DP where we keep track of the best answer so far for all possible input values.
# These start at zero.
# Now, say K = 3.
# When we process a new number, say 17, we find the best answer for 17 so far and
# add one -> say 8. Now we update CACHE[i] to 8 for i in {14,15,16,17,18,19,20}.
# Except we don't necessarily store 8, we store the max of 8 and whatever is
# currently there.

N, K = [int(x) for x in input().split()]

# Range of possible input values. We need to store best-answer-so-far for each of these.
RANGE = range(0, 300001)
CACHE = [0 for i in RANGE]

best = 0
for _ in range(N):
    # Read new value.
    A = int(input())
    # Determine current answer for that value.
    x = CACHE[A] + 1
    # Update the cache within K of this value.
    for i in range(A-K, A+K+1):
        if i in RANGE:
            CACHE[i] = max(CACHE[i], x)
    # Keep track of the best answer.
    best = max(best, x)

print(best)

Submission status: Time Limit Exceeded

Solution code:
def ceil_log2(n):
    i = 0
    while (1 << i) < n:
        i += 1
    return i


class SegmentTree:
    def __init__(self, values, e, op):
        if type(values) == int:
            values = [e] * values

        self._n = len(values)
        self._ceil_log2_n = ceil_log2(self._n)
        self._size = 1 << self._ceil_log2_n

        self._e = e
        
        self._op = op

        self._nodes = [e] * (2 * self._size)
        for i, value in enumerate(values):
            self._nodes[self._size + i] = value

        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, index, value):
        self._nodes[self._size + index] = value
        for i in range(1, self._ceil_log2_n + 1):
            self._update((self._size + index) >> i)

    def get(self, index):
        return self._nodes[self._size + index]

    def all_prod(self):
        return self._nodes[1]

    def prod(self, left, right):
        if left == right:
            return self._e

        if left == 0 and right == self._n:
            return self.all_prod()

        left_prod = self._e
        right_prod = self._e

        left += self._size
        right += self._size

        while left < right:
            if left & 1:
                left_prod = self._op(left_prod, self._nodes[left])
                left += 1

            if right & 1:
                right -= 1
                right_prod = self._op(self._nodes[right], right_prod)

            left >>= 1
            right >>= 1

        return self._op(left_prod, right_prod)

    def _update(self, index):
        self._nodes[index] = self._op(self._nodes[2 * index], self._nodes[2 * index + 1])


def main():
    n, k = map(int, input().split())
    arr = [int(input()) for _ in range(n)]

    overall_max_len = 0
    seg = SegmentTree(3 * 10 ** 5 + 1, 0, max)

    for value in arr:
        max_len = seg.prod(max(0, value - k), min(3 * 10 ** 5 + 1, value + k + 1)) + 1
        seg.set(value, max_len)
        overall_max_len = max(overall_max_len, max_len)

    print(overall_max_len)


main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
lis = []
for i in range(n): lis.append(int(input()))
dp = [1]*n
for i in range(n):
  for j in range(i):
    if abs(lis[i]-lis[j])<=3: dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy


def input():
    return sys.stdin.readline()[:-1]


class SegmentTree:

    def __init__(self, n, fn=lambda x, y: min(x, y), unity=(1 << 31) - 1):
        self.n = 1
        while self.n < n:
            self.n *= 2

        self.arr = [unity] * (2 * self.n - 1)
        self.fn = fn
        self.unity = unity

    def update(self, i, x):
        k = self.n + i - 1
        self.arr[k] = x

        while k > 0:
            k = (k - 1) // 2
            self.arr[k] = self.fn(self.arr[2 * k + 1], self.arr[2 * k + 2])

    def query(self, l, r):
        return self._inner_query(l, r, 0, 0, self.n)

    def _inner_query(self, l, r, k, il, ir):
        if ir <= l or r <= il:
            return self.unity

        elif l <= il and ir <= r:
            return self.arr[k]

        vl = self._inner_query(l, r, k * 2 + 1, il, (il + ir) // 2)
        vr = self._inner_query(l, r, k * 2 + 2, (il + ir) // 2, ir)
        return self.fn(vl, vr)

    def __str__(self):
        return self.arr[0: 2 * self.n].__str__()


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

st = SegmentTree(MAX + 10, fn=lambda x, y: max(x, y), unity=0)
ans = 0

while N > 0:
    A = int(input())
    minimum, maximum = max(A - K, 0), min(A + K, MAX)
    x = st.query(minimum, maximum + 1) + 1
    ans = max(ans, x)
    st.update(A, x)
    N -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy
import numpy as np

class SegmentTree:

    def __init__(self, n, fn=lambda x, y: min(x, y), unity=(1 << 31) - 1):
        self.n = 1
        while self.n < n:
            self.n *= 2

        self.arr = np.full(2 * self.n - 1, unity)
        self.fn = fn
        self.unity = unity

    def update(self, i, x):
        k = self.n + i - 1
        self.arr[k] = x

        while k > 0:
            k = (k - 1) // 2
            self.arr[k] = self.fn(self.arr[2 * k + 1], self.arr[2 * k + 2])

    def query(self, l, r):
        return self._inner_query(l, r, 0, 0, self.n)

    def _inner_query(self, l, r, k, il, ir):
        if ir <= l or r <= il:
            return self.unity

        elif l <= il and ir <= r:
            return self.arr[k]

        vl = self._inner_query(l, r, k * 2 + 1, il, (il + ir) // 2)
        vr = self._inner_query(l, r, k * 2 + 2, (il + ir) // 2, ir)
        return self.fn(vl, vr)

    def __str__(self):
        return self.arr[0: 2 * self.n].__str__()


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

st = SegmentTree(MAX + 10, fn=lambda x, y: max(x, y), unity=0)
ans = 0

while N > 0:
    A = int(input())
    minimum, maximum = max(A - K, 0), min(A + K, MAX)
    x = st.query(minimum, maximum + 1) + 1
    ans = max(ans, x)
    st.update(A, x)
    N -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy


class SegmentTree:


    def __init__(self, n, fn=lambda x, y: min(x, y), unity=(1 << 31) - 1):
        self.n = 1
        while self.n < n:
            self.n *= 2

        self.arr = [unity] * (2 * self.n - 1)
        self.fn = fn
        self.unity = unity

        self.lazy = [unity] * (2 * self.n - 1)
        self.flag = [False] * (2 * self.n - 1)


    def update(self, i, x):
        k = self.n + i - 1
        self.arr[k] = x

        while k > 0:
            k = (k - 1) // 2
            self.arr[k] = self.fn(self.arr[2 * k + 1], self.arr[2 * k + 2])

    def range_update(self, a, b, x):
        self._range_update(a, b, x, 0, 0, self.n)

    def _range_update(self, a, b, x, k, l, r):
        self._eval(k, l, r)

        if r <= a or b <= l:
            return
        elif a <= l and r <= b:
            self.flag[k] = True
            self.lazy[k] = x
            self._eval(k, l, r)
        else:
            self._range_update(a, b, x, 2 * k + 1, l, (l + r) // 2)
            self._range_update(a, b, x, 2 * k + 2, (l + r) // 2, r)
            self.arr[k] = self.fn(self.arr[2 * k + 1], self.arr[2 * k + 2])

    def _eval(self, k, l, r):
        if self.flag[k]:
            self.arr[k] = self.lazy[k]
            if l + 1 < r:
                self.lazy[2 * k + 1] = self.lazy[2 * k + 2] = self.lazy[k]
                self.flag[2 * k + 1] = self.flag[2 * k + 2] = True
            self.flag[k] = False

    def query(self, l, r):
        return self._inner_query(l, r, 0, 0, self.n)

    def _inner_query(self, l, r, k, il, ir):
        self._eval(k, il, ir)
        if ir <= l or r <= il:
            return self.unity

        elif l <= il and ir <= r:
            return self.arr[k]

        vl = self._inner_query(l, r, k * 2 + 1, il, (il + ir) // 2)
        vr = self._inner_query(l, r, k * 2 + 2, (il + ir) // 2, ir)
        return self.fn(vl, vr)

    def __str__(self):
        return self.arr[0: 2 * self.n].__str__()


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

st = SegmentTree(MAX + 10, fn=lambda x, y: max(x, y), unity=0)
ans = 0

for i in range(N):
    A = int(input())
    minimum, maximum = max(A - K, 0), min(A + K, MAX)
    x = st.query(minimum, maximum + 1) + 1
    ans = max(ans, x)
    st.update(A, x)

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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



ide_ele = -float('inf')


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=map(int,input().split())
a=[ int(input()) for _ in range(n)]
A=[0 for _ in range(303030)]
seg=SegTree(A,segfunc,ide_ele)
for x in a:
  seg.update(x,seg.query(max(0,x-k),min(303030,x+k+1))+1)
  
ans=seg.query(0,303030)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

n,k=map(int,input().split())
arr=[int(input()) for _ in range(n)]
lim=max(arr)
st=SegmentTreeMax(lim,0)
for val in arr:
  l=max(0,val-k)
  r=min(lim,val+k)
  tmp=st.query(l,r)
  st.update(val,tmp+1)
print(st.query(0,lim))

Submission status: Time Limit Exceeded

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

#####ide_ele#####
ide_ele = float('-inf')
#################

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 = map(int,input().split())
a = [0] * 300001
seg = SegTree(a, segfunc, ide_ele)
ans = 0
for _ in range(N):
    A = int(input())
    x = seg.query(max(0, A - K), min(300001, A + K + 1))
    seg.update(A, x + 1)
    ans = max(ans, x + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

class SegTree():
    """
    0-indexedの配列[a0, a1, a2, ..., a(N-1)]に対して以下のクエリをそれぞれO(logx)で行う：
        1. i番目の要素にxを代入
        2. 半開区間[i, j)内の最小値を返す
    self.id_elemとself.funcを変えることでRmQ以外にも例えばRMQに対応可能。
    参考：https://juppy.hatenablog.com/entry/2019/05/02/蟻本_python_セグメント木_競技プログラミング_Atcoder
    """
    def __init__(self, N):
        #####identity element######
        self.id_elem = 0
        self.func = max

        #num_max: the smallest power of two over N
        self.num_max = 2 ** ((N - 1).bit_length())
        self.x = [self.id_elem] * (2 * self.num_max - 1)

    def get_elem(self, i):
        """
        i番目の要素を返す
        """
        return self.x[self.num_max + i - 1]

    def update(self, i, x):
        """
        i番目の要素にxを代入
        """
        i += self.num_max - 1
        self.x[i] = x
        while (i > 0):
            i = (i - 1) // 2
            self.x[i] = self.func(self.x[i * 2 + 1], self.x[i * 2 + 2])

    def query(self, i=0, j=-1, k=0, l=0, r=-1):
        """
        半開区間[i, j)内の最小値を返す
        [l, r)はノードkに対応づく区間を与える
        query()で配列全体に対してクエリを実行する
        """
        if j == -1: j = self.num_max
        if r == -1: r = self.num_max

        # [i, j) and [l, r) are disjoint
        if (r <= i or j <= l): return self.id_elem
        # [l, r) is included in [i, j)
        if (i <= l and r <= j): return self.x[k]
        # [i, j] and [l, r) partially intersect
        vl = self.query(i, j, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(i, j, k * 2 + 2, (l + r) // 2, r)
        return self.func(vl, vr)

def main():
    N, K = map(int, input().split())
    """
    愚直に解けそうに無いのでdpを考える：dp[i][j] = (0~i番目まで見た時に最後の数がjで終わる部分列の最大長)
    このdpはO(N^2)なのでそのままでは実行不可能だが、ひとまず遷移を考えてみると
        dp[i][j] = max(dp[i-1][j-K], dp[i-1][j-K+1], ..., dp[i-1][j+K]) + 1
    ここのmaxをセグ木で導出すれば計算量はO(NlogN)で間に合う。
    """
    dp = SegTree(300001)
    for _ in range(N):
        a = int(input())
        # 最後がaで終わるケースのみ更新が入る
        now = dp.query(max(0, a - K), min(300001, a + K + 1))
        dp.update(a, now + 1)
    print(dp.query())


if __name__ == "__main__":
    main()