Problem:


Longest Increasing Subsequence

For a given sequence A = {a0, a1, ... , an-1}, find the length of the longest increasing subsequnece (LIS) in A.

An increasing subsequence of A is defined by a subsequence {ai0, ai1, ... , aik} where 0 ≤ i0 < i1 < ... < ik < n and ai0 < ai1 < ... < aik.

Input

n
a0
a1
:
an-1

In the first line, an integer n is given. In the next n lines, elements of A are given.

Output

The length of the longest increasing subsequence of A.

Constraints

1 ≤ n ≤ 100000

0 ≤ ai ≤ 109

Sample Input 1

5
5
1
3
2
4

Sample Output 1

3

Sample Input 2

3
1
1
1

Sample Output 2

1



Sample input:
5
5
1
3
2
4


Sample output:
3

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left
    n, *A = map(int, open(0).read().split())
    length = 0
    lis = []
    for a in A:
        i = bisect_left(lis, a)
        if i == length:
            lis.append(a)
            length += 1
        else:
            lis[i] = a
    print(length)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = [int(input()) for _ in range(n)]
# LIS
# 前から順番に埋めていく
# 順番に入る箇所を二分探索する bisect_right
# 1,3,3,4 3 -> 3 , 4-> 4
INF = 10 ** 9 + 1
dp = [INF] * n
ans = 0
for i in range(n):
    idx = bisect.bisect_left(dp, a[i])
    """
    if dp[idx - 1] == a[i]:  # 同じ数が並んできるケース
        continue
    """
    ans = max(idx + 1, ans)
    dp[idx] = a[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())

A = [0] * N
for i in range(N):
    A[i] = int(input())

dp = [0] * N

dp[0] = A[0]
cur = 1
for i in range(1, N):
    left = -1
    right = cur
    while right - left > 1:
        mid = left + (right - left) // 2
        if dp[mid] < A[i]:
            left = mid
        else:
            right = mid
    if cur == right:
        cur += 1
    dp[right] = A[i]
print(cur)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
INF = 10 ** 10
n = int(input())
alst = [int(input()) for _ in range(n)]
dp = [INF] * (n + 1)
dp[0] = -1
ans = 0
for a in alst:
  ind = bl(dp, a)
  dp[ind] = a
  ans = max(ans, ind)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

INF = 10**9 + 1
n = int(input())
dp = [INF] * (n+1)

for _ in range(n):
    a = int(input())
    i = bisect_left(dp, a)
    dp[i] = a
    # print(dp)
print(bisect_left(dp, INF))

Submission status: Accepted

Solution code:
import bisect


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

def LIS2(A):
    n = len(A)
    INF = max(A)+10
    L = [INF]*n
    length = 0

    for i in range(n):
        ins_ind = bisect.bisect_left(L,A[i])
        if length == ins_ind:
            length += 1
        L[ins_ind] = A[i]
    
    return length,L

L , _ = LIS2(A)
print(L)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())

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

LIS = [A[0]]                            # i番目の成分 = 長さ i+1 の増加部分列の最後の要素の値

for a in A[1:]:
    if a > LIS[-1]:                     # 最大の長さの増加部分列の最後の要素より大きい値なら、これを用いて１つ長い増加部分列を作ることができる。
                                        # 更新前の最長増加部分列 = [..., L[-1]]、更新後の最長増加部分列 = [..., L[-1], a]
        LIS.append(a)
    else:
        LIS[bisect_left(LIS, a)] = a    # 最長ではない増加部分列の最後の要素を小さい値に更新。これにより、a > LIS[-1] を満たす可能性が増える。

print(len(LIS))

Submission status: Accepted

Solution code:
from bisect import *
INF=10**18
n=int(input())
a=[int(input()) for i in range(n)]

dp=[INF]*(n+1)
dp[0]=-1
for i in range(n):
    b=bisect_left(dp,a[i])
    dp[b]=a[i]
ans=-1
for i in range(n+1):
    if dp[i]==INF:
        break
    ans=i
print(ans)

Submission status: Accepted

Solution code:
#最長増加部分列問題 (LIS) 
import bisect

N = int(input())
seq = [0] * N
for i in range(N):
  seq[i] = int(input())

LIS = [seq[0]]
#print(LIS)
for i in range(len(seq)):
    if seq[i] > LIS[-1]:
        LIS.append(seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
    #print(LIS)
#print(LIS)
print(len(LIS))

Submission status: Accepted

Solution code:
import sys
import bisect

input = sys.stdin.readline


def main():
    N = int(input())
    C = [int(input()) for _ in range(N)]

    x = []
    for c in C:
        if x:
            if x[-1] < c:
                x.append(c)
            else:
                y = bisect.bisect_left(x, c)
                x[y] = c
        else:
            x.append(c)

    print(len(x))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n= int(input())
a=[]
for _ in range(n):
    a.append(int(input()))

inf= 10**9
min_lis= [a[0]]
for i in range(1,n):
    if a[i]> min_lis[-1]:
        min_lis.append(a[i])
    else:
        min_lis[bisect.bisect_left(min_lis,a[i])]=a[i]
print(len(min_lis))
    
'''
if a==[3,1000000000,999999998,999999999]:
    res=2
print(res)
'''

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left
INF = 1 << 40

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    dp = [INF] * (N + 1)
    dp[0] = -1
    for a in A:
        idx = bisect_left(dp,a)
        dp[idx] = a
    ans = 1
    for i in range(N,-1,-1):
        if dp[i] < INF:
            ans = i
            break
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
    import bisect
    N=int(input())
    lists=[int(input()) for _ in range(N)]
    inf = 10**15
    dp=[inf  for i in range(N+1)]
    for i in range(N):
        index=bisect.bisect_left(dp,lists[i])
        dp[index]=lists[i]
    for i in range(N+1):
        if dp[i]==inf:
            print(i)
            break
if __name__=="__main__":
    solve()

Submission status: Accepted

Solution code:
import bisect

INF = 10 ** 9 + 1

N = int(input())
S = [int(input()) for l in range(N)]
L = [S[0]]

for i in range(1, N):
    if L[-1] < S[i]:
        L.append(S[i])
    else:
        L[bisect.bisect_left(L, S[i])] = S[i]

print(len(L))

Submission status: Accepted

Solution code:
import bisect

n=int(input())
seq=[int(input()) for _ in range(n)]

dp=[seq[0]]
for num in seq:
    if num > dp[-1]:
        dp.append(num)
    else:
        dp[bisect.bisect_left(dp,num)] = num

print(len(dp))

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D&lang=ja
from bisect import bisect_left
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,*A = map(int, read().split())

    LIS = [A[0]]
    for a in A:
        if a > LIS[-1]:
            LIS.append(a)
        else:
            LIS[bisect_left(LIS, a)] = a

    ans = len(LIS)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def lis(a):
    dp = [INF]*len(a)
    for i in a:
        idx = bisect.bisect_left(dp, i)
        dp[idx] = i
    return bisect.bisect_left(dp, INF)

def resolve():
    n = I()
    a = [I() for _ in range(n)]

    print(lis(a))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from bisect import bisect_left

INF = 10**9 + 1
n = int(input())
dp = [INF] * (n+1)

for _ in range(n):
    a = int(input())
    i = bisect_left(dp, a)
    dp[i] = a
    # print(dp)

print(bisect_left(dp, INF))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7
INF = 1 << 60

# ---------------------------------------------------
# ---------------------------------------------------
# ---------------------------------------------------
from bisect import bisect_left

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

    dp = [INF]*(N+1)
    for i in range(N):
        ind = bisect_left(dp, A[i])
        dp[ind] = A[i]

    ans = bisect_left(dp, INF)
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_D
import bisect

INF = float('inf')

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

dp = [INF for _ in range(n)]

for a in A:
    update_index = bisect.bisect_left(dp, a)
    dp[update_index] = a

print(bisect.bisect_left(dp, INF))

Submission status: Accepted

Solution code:
import bisect

INF = 10 ** 10


N = int(input())
dp = [INF] * (N + 1)
dp[0] = -1

ans = 0
for i in range(N):
    a = int(input())
    j = bisect.bisect_left(dp, a)
    dp[j]=a
    ans = max(j,ans)
print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
Ali = [int(input()) for _ in range(N)]
dp = [10**10]*N
dp[0] = Ali[0]

for i in range(1,N):
  a = Ali[i]
  if a > dp[i-1]:
    dp[i] = a
  else:
    dp[bisect.bisect_left(dp, a)] = a
    
print(bisect.bisect_left(dp, 10**10))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
def solve(N,A):
    lis = []
    for i in range(N):
        ind = bisect_left(lis,A[i])
        if ind == len(lis):
            lis.append(A[i])
        else:
            lis[ind] = A[i]
    ans = len(lis)
    return ans
print(solve(N,A))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = []
for _ in range(n):
    l.append(int(input()))

dp = [float('inf')]*n
# print()
for num in l:
    i = bisect.bisect_left(dp,num)
    # print(i)
    dp[i] = num
# print(dp)
for j in range(n):
    if dp[j] == float('inf'):
        print(j)
        exit()
print(n)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for _ in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
INF = float("inf")
import sys,bisect
sys.setrecursionlimit(15000)

n = int(sys.stdin.readline())
a = [int(sys.stdin.readline()) for _ in range(n)]

# naive O(n**2)
# dp = [0]*n
# for i in range(n):
#   m = 0
#   for j in range(0,i):
#     if a[j] < a[i] and m <= dp[j]:
#       m = dp[j]
#   dp[i] = m+1
# print(max(dp))
import bisect
dp = [float("inf")]*n
dp[0] = a[0]
l = 0
for i in range(1,n):
  if dp[l] < a[i]:
    l += 1
    dp[l] = a[i]
  else:
    j = bisect.bisect_left(dp,a[i])
    dp[j] = a[i]
print(bisect.bisect_left(dp,float("inf")))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*a = map(int,read().split())

#dp[i] = 長さiのLISの最後尾の最小値 
from bisect import bisect_left
INF = 2*10**9
dp = [INF]*n
for ai in a:
    dp[bisect_left(dp,ai)] = ai
ans = bisect_left(dp,INF)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
A = [int(input()) for _ in range(N)]


INF = 10 ** 10
dp = [INF] * N
res = 0
for i in range(N):
    idx = bisect_left(dp,A[i])
    dp[idx] = A[i]
print(bisect_left(dp, INF))

Submission status: Accepted

Solution code:
from bisect import bisect_right

def LIS(A):
    B = [INF for _ in range(len(A))]
    B[0] = A[0]
    for i in range(1,len(A)):
        pt = bisect_right(B,A[i])
        if B[pt-1] != A[i]:
            B[pt] = A[i]
    return bisect_right(B,INF-1)

n = int(input())
A = [int(input()) for _ in range(n)]
INF = 10**9+2

print(LIS(A))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

class Segtree: #1-indexed
    def __init__(self, n, A, segfunc, ide_ele):
        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] = A[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, ind, val): #0-indexed
        ind += self.num
        self.tree[ind] = val
        while ind > 1:
            self.tree[ind >> 1] = self.segfunc(self.tree[ind], self.tree[ind^1])
            ind >>= 1

    def find(self, l, r): #[1, r), 0-indexed
        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 = ii()
A = [ii() for i in range(N)]
compress = lambda arr: list(map({e: i for i, e in enumerate(sorted(set(arr)))}.__getitem__, arr))
A = compress(A)
'''
# 座標圧縮
d = defaultdict(int)
for i, num in enumerate(sorted(list(set(A)))):
    d[num] = i
for i, num in enumerate(A):
    A[i] = d[num]
'''
# Segtreeを用いたDP
dp = [0 for _ in range(N)]
seg = Segtree(N, dp, max, 0)

for num in A:
    dp[num] = seg.find(0, num) + 1
    seg.update(num, dp[num])

print(max(dp))

Submission status: Accepted

Solution code:
from bisect import bisect_left
n=int(input())
A=[int(input()) for _ in range(n)]

DP=[A[0]]
for i in range(1,n):
    num=A[i]
    if DP[-1]<num:
        DP.append(num)
    else:
        index=bisect_left(DP,num)
        DP[index]=num
print(len(DP))

Submission status: Accepted

Solution code:
from bisect import bisect_left

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


def LIS(arr):
	dp = [arr[0]]
	for i in arr[1:]:
		if dp[-1] < i:
			dp.append(i)
		else:
			dp[bisect_left(dp, i)] = i
	return len(dp)

print(LIS(A))

Submission status: Accepted

Solution code:
import bisect
n=int(input())
l=[float('inf')]*n
for i in range(n):
    a=int(input())
    p=bisect.bisect_left(l,a)
    l[p]=a
p=0
while p<n and l[p]!=float('inf'):
    p+=1
print(p)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
As = [int(input()) for _ in range(N)]

INF = 10**20
dp = [As[0]]

for i in range(1, N):
    a = As[i]
    if a>dp[-1]:
        dp.append(a)
    else:
        dp[bisect_left(dp, a)] = a
print(len(dp))

Submission status: Accepted

Solution code:
import bisect

N = int(raw_input())

LIS = []

for i in range(N):
    a = int(raw_input())
    z = bisect.bisect_left(LIS, a)
    if z >= len(LIS):
        LIS.append(a)
    else:
        LIS[z] = a

print len(LIS)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = [int(input()) for i in range(n)]
# n = 5
# A = [5, 1, 3, 2, 4]
L = [A[0]]
for i in range(n):
    if A[i] > L[-1]:
        L.append(A[i])
    else:
        j = bisect.bisect_left(L, A[i])
        L[j] = A[i]
print(len(L))

Submission status: Accepted

Solution code:
import bisect
N = int(input())
seq = [int(input()) for _ in range(N)]

LIS = [seq[0]]
for i in range(len(seq)):
    if seq[i] > LIS[-1]:
        LIS.append(seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]

print(len(LIS))

Submission status: Accepted

Solution code:
def LIS(seq: list) -> int:
    from bisect import bisect_left

    L = [seq[0]]
    for i in range(len(seq)):
        if seq[i] > L[-1]:
            L.append(seq[i])
        else:
            idx = bisect_left(L, seq[i])
            L[idx] = seq[i]
    return len(L)


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

Submission status: Accepted

Solution code:
n=int(input())
l=[]
from bisect import bisect_left
for i in range(n):
    a=int(input())
    if l==[]:
        l.append(a)
    else:
        if l[-1]<a:
            l.append(a)
        else:
            l[bisect_left(l,a)]=a

print(len(l))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input()) for _ in range(n)]
inf=10**10
l=[inf]*n
import bisect
for i in range(n):
	r=bisect.bisect_left(l,a[i])
	l[r]=a[i]
cnt=0
for i in range(n):
	if l[i]!=inf:
		cnt+=1
	else:
		break
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
A = [int(input()) for _ in range(n)]
INF = 10**18

dp = [INF]*(n+1)

dp[0] = -1

import bisect

for i in range(n):
    r_idx = bisect.bisect_right(dp, A[i])
    #print(r_idx)
    if dp[r_idx-1]<A[i] and dp[r_idx]>A[i]:
        dp[r_idx] = A[i]
        
ans = -1
dp.append(INF)
for i in range(n+2):
    if dp[i]==INF:
        ans = i-1 
        break

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
a = [int(input()) for _ in range(n)]

INF = 10**9
dp = [INF for _ in range(n)]
dp[0] = a[0]

for i in range(1, n):
    idx = bisect_left(dp, a[i])
    dp[idx] = a[i]

print(len(list(filter(lambda x: x != INF, dp))))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = IR(n)
    dp = [float("inf")]*n
    for i in a:
        j = bisect.bisect_left(dp,i)
        dp[j] = i
    print(n-dp.count(float("inf")))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

dp = [float("inf")] * n


for i in range(n):
    dp[bisect_left(dp, a[i])] = a[i]

print(bisect_left(dp, float("inf")))

Submission status: Accepted

Solution code:
from math import inf
import bisect

n = int(input())
A = [int(input()) for _ in range(n)]
dp = [inf] * n
for a in A:
    j = bisect.bisect_left(dp, a)
    dp[j] = a
ans = 0
for i in range(n):
    if dp[i] != inf:
        ans = i
print(ans + 1)

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 1 << ((self.n - 1).bit_length())
        self.op = op # operation
        self.e = e # identity element
        self.v = self._build(lst)
        
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N - 1 elements
        tree = [self.e] * (self.N - 1) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 2, -1, -1):
            tree[i] = self.op(tree[2*i + 1], tree[2*i + 2])
        return tree
    
    def __getitem__(self, i):
        return self.v[i + self.N - 1]
    
    # update a_i to be x 
    def update(self, i, x):
        i += self.N - 1
        self.v[i] = x
        while i > 0:
            i -= 1; i >>= 1
            self.v[i] = self.op(self.v[2*i + 1], self.v[2*i + 2])
    
    # returns answer for the query interval [l, r)
    def query(self, l, r):
        left = l + self.N - 1
        right = r + self.N - 1
        L = self.e; R = self.e
        while left < right:
            if left & 1 == 0: # self.v[left] is the right child
                L = self.op(L, self.v[left])
                left += 1
            if right & 1 == 0: # self.v[right-1] is the left child
                right -= 1
                R = self.op(self.v[right], R)
            left -= 1; left >>= 1
            right >>= 1
        return self.op(L, R)

def coord_compress(A):
    B = {a: i for i, a in enumerate(sorted(set(A)))}
    return [B[a] for a in A]
    
def LIS(A):
    A = coord_compress(A)
    dp = SegmentTree([0] * len(A), max, 0)
    for a in A:
        dp.update(a, max(dp[a], dp.query(0, a) + 1))
    return max(dp)

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

Submission status: Accepted

Solution code:
from bisect import bisect_left


def solve(n, sx):
    # Minimum value of last element in len(i+1) increasing subsequence.
    tbl = [float('inf')]*n
    # 5 6 9 1 10

    for i in range(n):
        idx = bisect_left(tbl, sx[i])
        tbl[idx] = sx[i]
        # [5,inf,inf,inf]
        # .
        # .
        # [5,6,9,inf,inf]
        # [1,6,9,inf,inf,]
        # [1,6,9,10,inf,]

    return bisect_left(tbl, float('inf'))


if __name__ == '__main__':
    n = int(input())
    sx = []
    for _ in range(n):
        sx.append(int(input()))

    print(solve(n, sx))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right, insort_left
from collections import deque


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = deque(sorted(ls))  # insertをO(1)にするためにlistの代わりにdequeを用います

    def __repr__(self):
        return f'BST:{self.bst}'

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        idx=self.bisect_left(x)
        self.bst.insert(idx ,x)

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) + 1
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


# load data
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))


L = BinarySearchTree()
L.insert(A[0])
length = 0
for a in A[1:]:
    L.insert_replace_right(a)
    # # もし最長増加部分列の中身が知りたいなら、新たに長さが更新されたときに最適であることが保証されている
    # if len(L) > length:
    #     length = len(L)
    #     LIS = L.bst

# print(LIS)
print(len(L))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]

li = [a[0]]
for i in a[1:]:
    if i > li[-1]:
        li.append(i)
    else:
        li[bisect.bisect_left(li,i)] = i
print (len(li))

Submission status: Accepted

Solution code:
# DPL_1_D - Longest Increasing Subsequence
from typing import Sequence


def longest_subsequence(A: Sequence[int], is_equal: bool, is_increasing: bool) -> int:
    """
    Compute the length of LIS or LDS.

    Args:
        A (Sequence[int]): a list or tuple to compute.
        is_equal (bool): permit adjacent numbers in subsequence to equal.
        is_increasing (bool): compute an increasing subsequence or decreasing one.
    Returns: (int) the length of a subsequence.
    """
    from bisect import bisect_left, bisect_right

    bs = bisect_right if is_equal else bisect_left
    compare = (lambda x, y: x >= y) if is_equal else (lambda x, y: x > y)
    if not is_increasing:
        A = A[::-1]

    dp = [A[0]]  # dp := length of LIS (dp table itself is not LIS)
    for i in A[1:]:
        if compare(i, dp[-1]):
            dp.append(i)
        else:
            dp[bs(dp, i)] = i
    return len(dp)


def main():
    N, *A = map(int, open(0))
    ans = longest_subsequence(A, is_equal=False, is_increasing=True)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def lis(N, A):
    from bisect import bisect_left

    # dp[i] := 長さがi以下の部分列で作られる最長部分増加列の最後の要素の最小値
    dp = [-1]  # A[i] >= 0 なのでそれ以下の値を設定し、数列の単調性を保つ
    for a in A:
        if dp[-1] < a:
            dp.append(a)
        else:
            # LISテーブルが単調増加であるため、aに更新される場所は1箇所しかあり得ず、二分探索で決定できる
            idx = bisect_left(dp, a)
            dp[idx] = a
    print(len(dp) - 1)

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

Submission status: Accepted

Solution code:
import bisect

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

que = [A[0]]

for a in A[1:]:
    if a > que[-1]:
        que.append(a)
    else:
        idx = bisect.bisect_left(que, a)
        que[idx] = a

print(len(que))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
LIS = [a[0]]
for i in range(n):
    if a[i] > LIS[-1]:
        LIS.append(a[i])
    else:
        LIS[bisect.bisect_left(LIS,a[i])] = a[i]
print(len(LIS))

Submission status: Accepted

Solution code:
from bisect import bisect_left

def LIS(arr):
    n = len(arr)
    lis = [arr[0]]
    for a in arr:
        if a > lis[-1]:
            lis.append(a)
        else:
            lis[bisect_left(lis,a)] = a
    return len(lis)

import sys
input = sys.stdin.readline

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

print(LIS(A))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def MF(): return map(float, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LF(): return list(map(float, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def main():
    n=II()
    lis=[]
    for _ in range(n):
        a=II()
        i=bisect_left(lis,a)
        if i==len(lis):lis.append(a)
        else:lis[i]=a
    print(len(lis))

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
aaa
"""
#import re #正規表現
import sys
import bisect
#import heapq
#import collections
#import math

def main():
    length = int(input())
    X = [0] * length
    for i, line in enumerate(sys.stdin): 
        X[i] = int(line)
    print(LIS2(X))

def LIS(X):
    res = 0
    N = len(X)
    dp = [1] * N
    for i in range(N):
        for j in range(i):
            if i == 0: dp[0] = 1
            elif X[i] > X[j]: dp[i] = max(dp[i], dp[j]+1)
        res = max(res, dp[i])
    return res

def LIS2(X):
    INF = 10 ** 10
    N = len(X)
    dp = [INF] * (N+1)
    dp[0] = -1
    for a in X:
        idx = bisect.bisect_right(dp, a-1)
        dp[idx] = min(a, dp[idx])
    return max(i for i in range(N+1) if dp[i] < INF)

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from bisect import bisect_left

def main():
    n = int(input().strip())
    a = [0] * n
    for i in range(n):
        a[i] = int(input().strip())
    l = [a[0]]
    for i in range(1, n):
        if a[i] <= l[-1]:
            k = bisect_left(l, a[i])
            l[k] = a[i]
        else:
            l.append(a[i])
    print(len(l))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    A = [int(input()) for i in range(N)]

    Inf = 10**9 + 1
    dp = [Inf] * N

    from bisect import bisect_left
    n = 0

    for a in A:
        i = bisect_left(dp, a, 0, n)

        if a < dp[i]:
            dp[i] = a
            n = max(n, i+1)
    print(n)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
import bisect

def input():
    return sys.stdin.readline()
def lis(n, A):
    L = [0 for i in range(n + 1)]
    L[0] = A[0]
    length = 1
    for i in range(1, n):
        if L[length - 1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            index = bisect.bisect_left(L, A[i], 0, length)
            L[index] = A[i]
    return length
if __name__=="__main__":
    n = int(input())
    A = [int(input()) for _ in range(n)]
    print(lis(n,A))

Submission status: Accepted

Solution code:
from bisect import bisect_left

dp = [-1]
n = int(input())
a = (int(input()) for _ in range(n))
for ai in a:
    if dp[-1] < ai:
        dp.append(ai)
    else:
        dp[bisect_left(dp, ai)] = ai
        
print(len(dp) - 1)

Submission status: Accepted

Solution code:

import bisect


def lis():
    L.append(A[0])
    length = 1
    
    for i in range(1, n):
        if L[length-1] < A[i]:
            L.append(A[i])
            length += 1
        else:
            if L[bisect.bisect_left(L, A[i])] >= A[i]:
                L[bisect.bisect_left(L, A[i])] = A[i]
            else:
                L[bisect.bisect_right(L, A[i])] = A[i]
    return length


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

print(lis())

Submission status: Accepted

Solution code:
def binary_search(sorted_list, a):
    left = 0
    right = len(sorted_list)
    while left < right:
        mid = (left + right) // 2
        if sorted_list[mid] < a:
            left = mid + 1
        else:
            right = mid
    return left


def lis(A):
    sorted_list = [10000000000]
    for a in A:
        if sorted_list[-1] < a:
            sorted_list.append(a)
        else:
            sorted_list[binary_search(sorted_list, a)] = a
    return len(sorted_list)
        

if __name__ == "__main__":
    n = int(input())
    a = [int(input()) for i in range(n)]

    print(lis(a))