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

Solution code:
def maxLenSub(arr, n, k): 
    mls=[] 
    max = 0
      
    #Initialize mls[] values for all indexes 
    for i in range(n): 
        mls.append(1) 
      
    #Compute optimized maximum length subsequence 
    # values in bottom up manner 
    for i in range(n): 
        for j in range(i): 
            if (abs(arr[i] - arr[j]) <= k and mls[i] < mls[j] + 1): 
                mls[i] = mls[j] + 1
                  
    # Store maximum of all 'mls' values in 'max' 
    for i in range(n): 
        if (max < mls[i]): 
            max = mls[i] 
      
    #required maximum length subsequence 
    return max
n, k = map(int, input().split())
aa = [int(input()) for _ in range(n)]

print(maxLenSub(aa, n, k))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)
input = lambda: sys.stdin.readline()


def scc(G):
    N = len(G)
    RG = [[] for _ in range(N)]

    for i, e in enumerate(G):
        for v in e:
            RG[v].append(i)

    order = []
    used = [0] * (N + 1)
    group = [None] * (N + 1)

    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)

    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)

    for i in range(N):
        if not used[i]:
            dfs(i)

    used = [0] * (N + 1)
    label = 0

    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1

    G0 = [set() for _ in range(label)]
    GP = [[] for _ in range(label)]

    for v in range(N):
        lbs = group[v]
        for w in G[v]:
            lbt = group[w]
            if lbs == lbt:
                continue
            G0[lbs].add(lbt)
        GP[lbs].append(v)
    return group, GP


class twosat():
    def __init__(self, n):
        self.n = n
        self.E = [[] for _ in range(n * 2)]

    def sat(self):
        group, GP = scc(self.E)
        re = [0] * self.n
        for i in range(self.n):
            if group[2 * i] == group[2 * i + 1]:
                return (0, [])
            if group[2 * i] < group[2 * i + 1]:
                re[i] = 1
        return (1, re)


n, d = map(int, input().split())
ts = twosat(n)
G = []
for _ in range(n):
    x = int(input())
    G.append(x)

for i, x1 in enumerate(G):
    for j, x2 in enumerate(G[:i]):
        if abs(x1 - x2) < d:
            ts.E[i * 2 + (1 ^ 1)].append(j * 2 + 1)
            ts.E[j * 2 + (1 ^ 1)].append(i * 2 + 1)

flg, re = ts.sat()
print(sum(re))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    
    BL = (300000).bit_length()
    WIDTH = pow(2, BL)
    BUFSIZE = pow(2, BL+1) - 1
    BASE = BUFSIZE - WIDTH
    
    # TODO: default value
    buf = [0] * BUFSIZE
    
    def update(i, x):
        i += BASE
        buf[i] = x
        i = (i-1) // 2
        while i >= 0:
            buf[i] = compare(buf[2*i+1], buf[2*i+2])
            i = (i-1) // 2
    
    # [q_left, q_right]
    def search(q_left, q_right):
        return _search(0, WIDTH, 0, q_left, q_right)
    
    def _search(l, width, i, q_left, q_right):
        if q_right < l or l + width - 1 < q_left:
            return 0
        if q_left <= l and l + width - 1 <= q_right:
            return buf[i]
        nwidth = width // 2
        c1 = _search(l, nwidth, 2*i+1, q_left, q_right)
        c2 = _search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
        return compare(c1, c2)
    
    def compare(i1, i2):
        if i1 > i2:
            return i1
        else:
            return i2
    
    for _ in range(N):
        a = int(input())
        maxlen = search(a-K, a+K)
        update(a, maxlen+1)
    print(search(0, 300000))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)


@lru_cache(None)
def dp(i, prev):
    if i == N:
        return 0
    else:
        if prev is None or abs(A[i] - prev) <= K:
            return max(dp(i + 1, prev), dp(i + 1, A[i]) + 1)
        else:
            return dp(i + 1, prev)

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
print(dp(0, None))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)


@lru_cache(None)
def dp(i, prev):
    if i == N:
        return 0
    else:
        if prev is None or abs(A[i] - prev) <= K:
            return max(dp(i + 1, prev), dp(i + 1, A[i]) + 1)
        else:
            return dp(i + 1, prev)

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
print(dp(0, None))

Submission status: Time Limit Exceeded

Solution code:
# SHRI GANESHA    author: Kunal Verma#

import os,sys
from collections import defaultdict
from io import BytesIO, IOBase




def main():
    n,k = map(int,input().split())
    a=[int(input()) for x in range(n)]
    dp=[1 for i in range(n)]
    for i in range(n):
        for j in range(i):
            if abs(a[j]-a[i])<=k:
                
                dp[i]=max(dp[i],dp[j]+1)
    print(dp[n-1])



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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, iterable, op, e):
        n = len(iterable)
        self._op = op
        self._e = e
        self._size = n
        t = 1 << (n - 1).bit_length()
        self._offset = t - 1
        self._data = [e] * (t * 2 - 1)
        self._data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = op(self._data[i * 2 + 1], self._data[i * 2 + 2])
 
    def __getitem__(self, key):
        return self._data[self._offset + key]
 
    def __setitem__(self, key, value):
        op = self._op
        data = self._data
        i = self._offset + key
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])
 
    def query(self, start, end):
        op = self._op
        res = self._e
        l = self._offset + start
        r = self._offset + end
        while l < r:
            if l & 1 == 0:
                res = op(res, self._data[l])
            if r & 1 == 0:
                r -= 1
                res = op(res, self._data[r])
            l = l // 2
            r = r // 2
        return res
    
    def getTop(self):
        return self._data[0]
 
N,K=map(int,input().split())
A = []
for i in range(N):
  a = int(input())
  A.append(a)
 
A_MAX = 300000
dp = [0]*(A_MAX+5)
 
st = SegmentTree(dp,max,0)

for i in range(N):
  s = max(A[i]-K, 0)
  e = min(A[i]+K+1, A_MAX+1)
  st[A[i]] = st.query(s, e) + 1
print(st.getTop())

Submission status: Accepted

Solution code:
# 0-index segment tree


class SegmentTree:
    """
    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: セグメント木(0-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 - 1 + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 2, -1, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num - 1
        # self.tree[k]  = x   <- when updated
        # self.tree[k] += x  <- when added
        self.tree[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = self.segfunc(self.tree[2 * k + 1], self.tree[2 * k + 2])

    def query(self, left, right):

        if left >= right:
            print("left must be smaller than right")
            exit(0)

        if right > self.num:
            print("right must be smaller than self.num")
            exit(0)

        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        left += self.num - 1
        right += self.num - 1
        while left < right:
            if left & 1 == 0:
                res = self.segfunc(res, self.tree[left])
            if right & 1 == 0:
                right -= 1
                res = self.segfunc(res, self.tree[right])
            left >>= 1
            right >>= 1
        return res


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

a = []
for i in range(n):
    a.append(int(input()))

dp = [0] * (MAX_NUM + 5)

segfunc = max
ide_ele = -float("inf")

st = SegmentTree(dp, segfunc, ide_ele)

for num in a:
    left = max(0, num - k)
    right = min(MAX_NUM, num + k) + 1

    st.update(num, st.query(left, right) + 1)

print(st.query(0, MAX_NUM + 1))

Submission status: Accepted

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

n = 300002

def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res

#####単位元######
ide_ele_max = -1

#num_max:n以上の最小の2のべき乗
num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

A = [0]*300002
init_max(A)

for i in range(_N):
    update_max(a[i], query_max(max(0, a[i]-k), min(300001, a[i]+k+1))+1)

print(query_max(0,300001))

Submission status: Accepted

Solution code:
from sys import stdin
read = stdin.read
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())

MAX_A = 300005

class SegmentTree:
    def __init__(self, n:int, p:list, ide_ele, func):
        self.num = 1 << ((n-1).bit_length())
        self.tree = [ide_ele]*(2*self.num)
        for i in range(n):
            self.tree[i+self.num] = p[i]
        for i in range(self.num-1, 0, -1):
            self.tree[i] = func(self.tree[i << 1], self.tree[(i << 1)+1])
        self.f = func
        self.ide_ele = ide_ele

    def update(self, i, x):
        i += self.num
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.f(self.tree[i << 1], self.tree[(i << 1)+1])

    def query(self, l, r):
        ansl = ansr = self.ide_ele
        l += self.num
        r += self.num-1
        if l == r:
            return self.tree[l]
        while l < r:
            if l & 1:
                ansl = self.f(ansl, self.tree[l])
                l += 1
            if ~r & 1:
                ansr = self.f(self.tree[r], ansr)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            ansl = self.f(ansl, self.tree[l])
        return self.f(ansl, ansr)

def main():
    N, K = i_map()
    A = list(map(int, read().strip().splitlines()))
    s = SegmentTree(MAX_A, [0]*MAX_A, 0, lambda x, y : max(x,y))
    ans = 0
    for a in A:
        l, r = max(a - K, 0), min(a + K + 1, MAX_A)
        now = s.query(l, r) + 1
        s.update(a, now)
        ans = max(ans, now)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
read = stdin.read
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())

MAX_A = 300005

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] = 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):
        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 = i_map()
    A = list(map(int, read().strip().splitlines()))
    s = SegTree([0]*MAX_A, lambda x, y : max(x,y), 0)
    ans = 0
    for a in A:
        l, r = max(a - K, 0), min(a + K + 1, MAX_A)
        now = s.query(l, r) + 1
        s.update(a, now)
        ans = max(ans, now)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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