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 typing

def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1
    return x

def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2
    return x

class SegTree:
    def __init__(self,
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 e: typing.Any,
                 v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)

        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        p += self._size
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        return self._d[p + self._size]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        sml = self._e
        smr = self._e
        left += self._size
        right += self._size

        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def max_right(self, left: int,
                  f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert f(self._e)

        if left == self._n:
            return self._n
    
    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

n, k, *A = map(int, open(0).read().split())
m = 303030
segtree = SegTree(op=max, e=0, v=m)
for a in A:
    l, r = max(1, a-k), min(m, a+k+1)
    segtree.set(a, segtree.prod(l, r)+1)
print(segtree.all_prod())

Submission status: Wrong Answer

Solution code:
import typing

def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1
    return x

def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2
    return x

class SegTree:
    def __init__(self,
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 e: typing.Any,
                 v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)

        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        p += self._size
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        return self._d[p + self._size]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        sml = self._e
        smr = self._e
        left += self._size
        right += self._size

        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def max_right(self, left: int,
                  f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert f(self._e)

        if left == self._n:
            return self._n
    
    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

n, k, *A = map(int, open(0).read().split())
m = max(A)+1
segtree = SegTree(op=max, e=0, v=m)
for a in A:
    l, r = max(1, a-k), min(m, a+k+1)
    segtree.set(a, max(segtree.get(a), segtree.prod(l, r)+1))
print(segtree.all_prod())

Submission status: Wrong Answer

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

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

ans=[]

left=a[0]
ans.append(left)

for i in range(n-1):
    if abs(left-a[i+1])<=k:
        left=a[i+1]
        ans.append(left)

print(len(ans))

Submission status: Wrong Answer

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

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

ans=0

left=a[0]

for i in range(n-1):
    if abs(left-a[i+1])<=k:
        left=a[i+1]
        ans+=1
if left==a[-1]:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:


class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x, y: x+y, default=0):
        self.size = 2**(size-1).bit_length()  # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2)  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                # モノイドでは可換律は保証されていないので演算の方向に注意
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


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

A = [int(input()) for _ in range(N)]

st = SegmentTree(300000+10, f=max)

res = 0
for sa in A:
    L = max(sa-K, 0)
    R = min(sa+K+1, 300001)

    tmp = st.query(L, R+1)+1
    st.update(sa, tmp)
    res = max(tmp, res)

print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N, K = MI()
    A = []
    max_a = 0
    for i in range(N):
        a = II()
        A.append(a)
        max_a = max(max_a, a)

    dp = [0] * N
    last_index = [-1] * (max_a + 1)

    for i in range(N):
        pres = []
        target = A[i]
        for k in range(target-3, target+4):
            if k < 0 or k > max_a:
                continue
            if last_index[k] == -1:
                pres.append(1)
                continue
            pres.append(dp[last_index[k]] + 1)
        dp[i] = max(pres)
        last_index[target] = i

    print(max(dp))


main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

S=[]
for i in range(19):
    #S.append([0]*2**i)
    S.append([0]*300010)
S.append([0]*300010)

ans=0
for i in range(N):
    A=int(input())
    R=min(A+K,300000)
    L=max(A-K,0)

    #tmp=max(S[19][L:(R+1)])+1
    M=[]
    j=19
    while(1):
        if L==R:
            M.append(S[j][L])
            break

        if R%2==0:
            M.append(S[j][R])
            R=R//2-1
        else:
            R=R//2

        if L%2==1:
            M.append(S[j][L])
            L=L//2+1
        else:
            L=L//2

        j-=1
        if j<0: break
        
    tmp=max(M)+1
    ans=max(tmp,ans)

    #S[A]=tmp
    S[19][A]=tmp
    for j in range(18,-1,-1):
        a=A//2
        if A%2==0:
            B=A+1
        else:
            B=A-1
        S[j][a]=max(S[j+1][A],S[j+1][B])
        A=a
    
    
print(ans)

Submission status: Wrong Answer

Solution code:
class SegTree(object):
  def __init__(self,op,e,n,init_val):
    self.num = 1<<(n-1).bit_length() 
    self.S = [e]*self.num*2
    self.op = op
    self.e = e
    for i,v in enumerate(init_val): self.S[self.num+i] = v
    for i in range(self.num-1,0,-1):
      self.S[i] = self.op(self.S[i*2], self.S[i*2+1])
      
  def set(self,index,value):
    idx = self.num+index
    self.S[idx] = value
    while idx>0:
      self.S[idx>>1] = self.op(self.S[idx],self.S[idx^1])
      idx>>=1
      
  def prod(self,l,r):
    res = self.e
    l = max(0,l)+self.num
    r = min(r,self.num-1)+self.num
    while l<r:
      if l&1:
        res = self.op(res,self.S[l])
        l += 1
      if r&1:
        res = self.op(self.S[r-1],res)
      l >>= 1
      r >>= 1
    return res
        
N,K = map(int,input().split())
ST = SegTree(max,0,300001,[0]*300001)
ans = 1
for i in range(N):
  A = int(input())
  l,r = max(0,A-K),min(A+K+1,300000)
  v = ST.prod(l,r)+1
  ans = max(ans,v)
  ST.set(A,v)
print(ans)

Submission status: Wrong Answer

Solution code:
class SegTree(object):
  def __init__(self,op,e,n,init_val):
    self.num = 1<<(n-1).bit_length() 
    self.S = [e]*self.num*2
    self.op = op
    self.e = e
    for i,v in enumerate(init_val): self.S[self.num+i] = v
    for i in range(self.num-1,0,-1):
      self.S[i] = self.op(self.S[i*2], self.S[i*2+1])
      
  def set(self,index,value):
    idx = self.num+index
    self.S[idx] = value
    while idx>0:
      self.S[idx>>1] = self.op(self.S[idx],self.S[idx^1])
      idx>>=1
      
  def prod(self,l,r):
    res = self.e
    l = max(0,l)+self.num
    r = min(r,self.num-1)+self.num
    while l<r:
      if l&1:
        res = self.op(res,self.S[l])
        l += 1
      if r&1:
        res = self.op(self.S[r-1],res)
      l >>= 1
      r >>= 1
    return res
        
N,K = map(int,input().split())
ST = SegTree(max,0,300000,[0]*300000)
ans = 1
for i in range(N):
  A = int(input())-1
  l,r = max(0,A-K),min(A+K+1,300000)
  v = ST.prod(l,r)+1
  ans = max(ans,v)
  ST.set(A,v)
print(ans)

Submission status: Wrong Answer

Solution code:
class SegTree(object):
  def __init__(self,op,e,n,init_val):
    self.num = 1<<(n-1).bit_length() 
    self.S = [e]*self.num*2
    self.op = op
    self.e = e
    for i,v in enumerate(init_val): self.S[self.num+i] = v
    for i in range(self.num-1,0,-1):
      self.S[i] = self.op(self.S[i*2], self.S[i*2+1])
      
  def set(self,index,value):
    idx = self.num+index
    self.S[idx] = value
    while idx>0:
      self.S[idx>>1] = self.op(self.S[idx],self.S[idx^1])
      idx>>=1
      
  def prod(self,l,r):
    res = self.e
    l = max(0,l)+self.num
    r = min(r,self.num-1)+self.num
    while l<r:
      if l&1:
        res = self.op(res,self.S[l])
        l += 1
      if r&1:
        res = self.op(self.S[r-1],res)
      l >>= 1
      r >>= 1
    return res
        
N,K = map(int,input().split())
ST = SegTree(max,0,300000,[0]*300000)
ans = 1
for i in range(N):
  A = int(input())-1
  v = ST.prod(A-K,A+K+1)+1
  ans = max(ans,v)
  ST.set(A,v)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
n = 300001

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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = -1

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

A = [0]*(300005)
init(A)

for _ in range(N):
    a = int(input())
    nax = query(max(0,a-K),min(300001,a+K+1))
    if nax >= A[a]:
        update(a,nax+1)
    
print(query(0,30001))

Submission status: Wrong Answer

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

count=0

for i in range(0,n-1):
    for j in range(i+1,n-1):
        if j==n-1:
            break
        elif abs(a[i]-a[j])<=k:
            count+=1
            break

print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
N,K=map(int, sys.stdin.readline().split())
A=[ int(sys.stdin.readline().strip()) for _ in range(N) ]
max_A=max(A)

# max_Aが処理する区間の長さ
N0 = 2**(3*10**5-1).bit_length()
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最大値
def query(l, r):
    L = l + N0; R = r + N0
    s = float("-inf")
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i,a in enumerate(A):
    update(a,query(max(a-K,1),min(a+K+1,max_A+1))+1)

print query(0,max_A+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
N,K=map(int, sys.stdin.readline().split())
A=[ int(sys.stdin.readline().strip()) for _ in range(N) ]
max_A=max(A)

# max_Aが処理する区間の長さ
N0 = 2**(max_A-1).bit_length()
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最大値
def query(l, r):
    L = l + N0; R = r + N0
    s = float("-inf")
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i,a in enumerate(A):
    update(a,query(max(a-K,1),min(a+K+1,max_A+1))+1)

print query(0,max_A+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
N,K=map(int, sys.stdin.readline().split())
A=[ int(sys.stdin.readline().strip()) for _ in range(N) ]
max_A=max(A)

# max_Aが処理する区間の長さ
N0 = 2**(max_A-1).bit_length()
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最大値
def query(l, r):
    L = l + N0; R = r + N0
    s = float("-inf")
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i,a in enumerate(A):
    update(a,query(max(a-K,1),min(a+K+1,max_A+1))+1)

print query(1,max_A+1)

Submission status: Wrong Answer

Solution code:
def segfunc(x,y):#自分で設定
    return max(x,y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele = -1 #単位元 自分で設定してね

N , K = map(int,input().split())
n = 300001
num =2**(300000).bit_length() #num:n以上の最小の2のべき乗
seg=[ide_ele]*2*num
a = [int(input()) for i in range(N)]
dp = [1 for i in range(300001)]
init(dp)

for i in range(N):
    now = query(max(0,a[i]-K),min(300000,a[i]+K))+1
    update(a[i],now)

print(query(0,300001))

Submission status: Wrong Answer

Solution code:
def segfunc(x,y):#自分で設定
    return max(x,y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele = -1 #単位元 自分で設定してね

N , K = map(int,input().split())
n = 300001
num =2**(300000).bit_length() #num:n以上の最小の2のべき乗
seg=[ide_ele]*2*num
a = [int(input()) for i in range(N)]
dp = [1 for i in range(300001)]
init(dp)

for i in range(N):
    now = query(max(0,a[i]-K),min(300000,a[i]+K))+1
    update(a[i],now)

print(max(seg))

Submission status: Wrong Answer

Solution code:
def segfunc(x,y):#自分で設定
    return max(x,y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele = -1 #単位元 自分で設定してね

N , K = map(int,input().split())
n = 300001
num =2**(300000).bit_length() #num:n以上の最小の2のべき乗
seg=[ide_ele]*2*num
a = [int(input()) for i in range(N)]
dp = [1 for i in range(300001)]
init(dp)
for i in range(N):
    now = query(max(0,a[i]-K),min(300000,a[i]+K))+1
    if dp[a[i]] < now:
        update(a[i],now)

print(max(seg))

Submission status: Wrong Answer

Solution code:

## https://atcoder.jp/contests/abc170/submissions/14416787
class SegmentTree():
    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

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]

st=SegmentTree(300001,0)
##セグ木の挙動が追えない
for ai in a:
    l=max(0,ai-k-1)
    r=min(300001,ai+k)
    m=st.query(l,r)
    st.update(ai-1,m+1)

print(st.query(0,300001))

Submission status: Wrong Answer

Solution code:

## https://atcoder.jp/contests/abc170/submissions/14416787
class SegmentTree():
    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

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]

st=SegmentTree(300001,0)

for ai in a:
    l=max(0,ai-k)
    r=min(300001,ai+k+1)
    m=st.query(l,r)
    st.update(ai,m+1)

print(st.query(0,300001))

Submission status: Wrong Answer

Solution code:

## https://atcoder.jp/contests/abc170/submissions/14416787
class SegmentTree():
    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

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]

st=SegmentTree(300001,0)

for ai in a:
    l=max(0,ai-k)
    r=min(n+1,ai+k+1)
    m=st.query(l,r)
    st.update(ai,m+1)

print(st.query(0,300001))

Submission status: Wrong Answer

Solution code:

## https://atcoder.jp/contests/abc170/submissions/14416787
class SegmentTree():
    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

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]

st=SegmentTree(300001,0)

for ai in a:
    l=max(0,ai-k)
    r=min(n+1,ai+k+1)
    m=st.query(l,r)
    st.update(ai,m+1)

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

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
ans,n = 1,1
dp = [1]*N
As = [0]*N
for i in range(N):
  As[i] = Ai = int(input())
  n = max(0,i-500)
  for j,Aj in enumerate(As[n:i]):
    j += n
    if abs(Ai-Aj)<=K: dp[i] = max(dp[i],dp[j]+1)
print(dp[-1])

Submission status: Wrong Answer

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

ide_ele = 0

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)のsegfuncしたものを得る
        """
        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())
T = []
for i in range(N):
    a = int(input())
    T.append(a)

A = [0]*(max(T)+1)
s_tree = segtree(A, segfunc, ide_ele)
for i in range(N):
    a = T[i]
    p = s_tree.query(max(a - K, 0), min(a + K + 1, 30001))
    s_tree.update(a, p + 1)

print(s_tree.query(0, max(T)+1))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
ans,n = 1,1
dp = [1]*N
As = []
for i in range(N):
  Ai = int(input())
  n = max(0,i-200)
  for j,Aj in enumerate(As[n:]):
    j += n
    if abs(Ai-Aj)<=K: dp[i] = max(dp[i],dp[j]+1)
  As.append(Ai)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
ans,n = 1,1
dp = [1]*N
As = []
for i in range(N):
  Ai = int(input())
  n = max(0,i-100)
  for j,Aj in enumerate(As[n:]):
    j += n
    if abs(Ai-Aj)<=K: dp[i] = max(dp[i],dp[j]+1)
  As.append(Ai)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
ans,n = 1,1
dp = [1]*N
As = []
for i in range(N):
  Ai = int(input())
  for j,Aj in enumerate(As[max(0,i-1000):]):
    if abs(Ai-Aj)<=K: dp[i] = max(dp[i],dp[j]+1)
  As.append(Ai)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
class segtree:

    def __init__(self, n, operator, identity):
        # identityは初期値
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2 ** (len(nb) - 1)
        else:
            self.num_end_leaves = 2 ** (len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator = operator

    def update(self, x, val):
        actual_x = x + self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0:
            actual_x = actual_x // 2
            self.array[actual_x] = self.operator(self.array[actual_x * 2], self.array[actual_x * 2 + 1])

    def get(self, q_left, q_right, arr_ind=1, leaf_left=0, depth=0):
        width_of_floor = self.num_end_leaves // (2 ** depth)
        leaf_right = leaf_left + width_of_floor - 1

        if leaf_left > q_right or leaf_right < q_left:
            return self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left, q_right, 2 * arr_ind, leaf_left, depth + 1)
            val_r = self.get(q_left, q_right, 2 * arr_ind + 1, leaf_left + width_of_floor // 2, depth + 1)
            return self.operator(val_l, val_r)


N, K = map(int, input().split())
T = []
for i in range(N):
    a = int(input())
    T.append(a)

s_tree = segtree(max(T)+1, max, 0)
for i in range(N):
    a = T[i]
    p = s_tree.get(max(a - K, 0), min(a + K, 30000))
    s_tree.update(a, p + 1)
print(s_tree.get(0, max(T)))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
ans,n = 1,1
dp = [1]*N
As = []
for i in range(N):
  Ai = int(input())
  for j,Aj in enumerate(As[max(0,i-100):]):
    if abs(Ai-Aj)<=K: dp[i] = max(dp[i],dp[j]+1)
  As.append(Ai)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
ans,n = 1,1
dp = [1]*N
As = [0]*N
for i in range(N):
  As[i] = Ai = int(input())
  for j,Aj in enumerate(As[max(0,i-100):i]):
    if abs(Ai-Aj)<=K: dp[i] = max(dp[i],dp[j]+1)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
class segtree:

    def __init__(self, n, operator, identity):
        # identityは初期値
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2 ** (len(nb) - 1)
        else:
            self.num_end_leaves = 2 ** (len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator = operator

    def update(self, x, val):
        actual_x = x + self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0:
            actual_x = actual_x // 2
            self.array[actual_x] = self.operator(self.array[actual_x * 2], self.array[actual_x * 2 + 1])

    def get(self, q_left, q_right, arr_ind=1, leaf_left=0, depth=0):
        width_of_floor = self.num_end_leaves // (2 ** depth)
        leaf_right = leaf_left + width_of_floor - 1

        if leaf_left > q_right or leaf_right < q_left:
            return self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left, q_right, 2 * arr_ind, leaf_left, depth + 1)
            val_r = self.get(q_left, q_right, 2 * arr_ind + 1, leaf_left + width_of_floor // 2, depth + 1)
            return self.operator(val_l, val_r)


N, K = map(int, input().split())
s_tree = segtree(300001, max, 0)  # 10**5までの配列なので適当に単位元は10**9
for i in range(N):
    a = int(input())
    p = s_tree.get(max(a-K, 0), min(a+K, 30000))
    s_tree.update(a, p+1)

print(s_tree.get(0, 30000))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
N,K=map(int, sys.stdin.readline().split())
A=[ int(sys.stdin.readline().strip()) for _ in range(N) ]
max_A=max(A)

# max_Aが処理する区間の長さ
N0 = 2**(max_A-1).bit_length()
data = [float("-inf")]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = float("-inf")
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i,a in enumerate(A):
    if i==0:
        update(a,1)
    else:
        update(a,query(max(a-K,1),min(a+K+1,max_A+1))+1)

print query(1,max_A+1)

Submission status: Wrong Answer

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

l[0].append(a[0])
ans=0
for ai in a[1:]:
  for i in reversed(range(ans+1)): # if can a_i put backword, add l[i+1]. because of maximum length answer 
    for li in l[i]:
      if -k<=(li-ai)<=k:
        ans=max(ans,i+1)
        l[ans].append(ai)
        break
    else:
      continue
    break
  else:
    l[0].append(ai)

print(ans+1)

Submission status: Wrong Answer

Solution code:
line = input().rstrip().split(" ")
num = int(line[0])
diffirence = int(line[1])
lastdigit = int(input().rstrip())
answerlist = [lastdigit]

for i in range(num - 1):
    digit = int(input().rstrip())
    if abs(digit - lastdigit) <= diffirence:
        answerlist.append(digit)
        lastdigit = digit

print(len(answerlist))