Submission #17045619


Source Code Expand

Copy
import sys
def input(): return sys.stdin.readline().rstrip()
from fractions import gcd
class seg():
    def __init__(self,init_val):
        self.n=len(init_val)
        self.ide_ele= 0 #単位元
        self.num=2**(self.n-1).bit_length() #n以上の最小の2のべき乗
        self.seg=[self.ide_ele]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num-1]=init_val[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.seg_func(self.seg[2*i+1],self.seg[2*i+2])
    def seg_func(self,a,b):
        #return a+b #0
        #return a*b #1
        #return gcd(a,b) #0
        return max(a,b) #0か-1か-10**10 (十分小さいもの,計算に使う場合0)
        #return min(a,b) #10**10 (十分大きいもの)
    def update(self,k,x):
        k+=self.num-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.seg_func(self.seg[k*2+1],self.seg[k*2+2])
    def query(self,p,q): #O(logN)
        if q<=p:return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        self.res=self.ide_ele
        while q-p>1:
            if p&1==0:
                self.res=self.seg_func(self.res,self.seg[p])
            if q&1==1:
                self.res=self.seg_func(self.res,self.seg[q])
                q-=1
            p=p//2
            q=(q-1)//2
        if p==q:self.res=self.seg_func(self.res,self.seg[p])
        else:self.res=self.seg_func(self.seg_func(self.res,self.seg[p]),self.seg[q])
        return self.res

def main():
    n, k = map(int,input().split())
    A = [int(input())for _ in range(n)]
    max_a = max(A)
    A_len = [0] * (max_a + 1) # 最後の数字がiのときの最大長さ
    SEG = seg(A_len)
    for a in A:
        SEG.update(a, SEG.query(max(a - k, 0), min(a + k, max_a) + 1) + 1)
    print(SEG.query(0, max_a + 1))

if __name__=='__main__':
    main()

Submission Info

Submission Time
Task D - Flat Subsequence
User charter
Language PyPy3 (7.3.0)
Score 400
Code Size 1927 Byte
Status
Exec Time 872 ms
Memory 103196 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
× 1
× 31
Set Name Test Cases
Sample example0.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, example0.txt
Case Name Status Exec Time Memory
000.txt 872 ms 97352 KB
001.txt 260 ms 87236 KB
002.txt 269 ms 87460 KB
003.txt 370 ms 91644 KB
004.txt 227 ms 86688 KB
005.txt 314 ms 90576 KB
006.txt 385 ms 93220 KB
007.txt 451 ms 97016 KB
008.txt 256 ms 88268 KB
009.txt 267 ms 87440 KB
010.txt 511 ms 102400 KB
011.txt 530 ms 102280 KB
012.txt 515 ms 102204 KB
013.txt 541 ms 102608 KB
014.txt 508 ms 102016 KB
015.txt 522 ms 101892 KB
016.txt 541 ms 102820 KB
017.txt 514 ms 102612 KB
018.txt 516 ms 102040 KB
019.txt 534 ms 102220 KB
020.txt 444 ms 101644 KB
021.txt 506 ms 103196 KB
022.txt 493 ms 102068 KB
023.txt 509 ms 102044 KB
024.txt 521 ms 100412 KB
025.txt 488 ms 102368 KB
026.txt 480 ms 102624 KB
027.txt 512 ms 102308 KB
028.txt 424 ms 101952 KB
029.txt 411 ms 101616 KB
example0.txt 90 ms 72656 KB