Problem:


Score : 500 points

Problem Statement

You are given a sequence with N integers: A = \{ A_1, A_2, \cdots, A_N \}.
For each of these N integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:

If A_i and A_j (i < j) are painted with the same color, A_i < A_j.

Find the minimum number of colors required to satisfy the condition.

Constraints

1 \leq N \leq 10^5

0 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the minimum number of colors required to satisfy the condition.

Sample Input 1

5
2
1
4
5
3

Sample Output 1

2

We can satisfy the condition with two colors by, for example, painting 2 and 3 red and painting 1, 4, and 5 blue.

Sample Input 2

4
0
0
0
0

Sample Output 2

4

We have to paint all the integers with distinct colors.



Sample input:
5
2
1
4
5
3


Sample output:
2

Submission status: Accepted

Solution code:
import bisect
from collections import deque
N = int(input())
nums = deque([])

for i in range(N):
    num = int(input())
    if i == 0:
        nums.append(num)
    else:
        if nums[-1] < num:
            nums[-1] = num
        else:
            insert_index = bisect.bisect_left(nums, num)
            if insert_index == 0:
                nums.appendleft(num)
            else:
                nums[insert_index - 1] = num
#     print(nums)
# print(nums)
print(len(nums))

Submission status: Accepted

Solution code:
from bisect import bisect_right, insort_right
N = int(input())
A = [int(input()) for _ in range(N)][::-1]
res = [A[0]]
for a in A[1:]:
    idx = bisect_right(res, a)
    if idx == len(res):
        res.append(a)
    else:
        if res[idx] == a:
            insort_right(res, a)   
        else:
            res[idx] = a
print(len(res))

Submission status: Accepted

Solution code:
from bisect import bisect_right

N, *A = map(int, open(0).read().split())

x = [1] * (N + 1)
for i in range(N):
    j = bisect_right(x, -A[i])
    x[j] = -A[i]
print(sum(v != 1 for v in x))

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

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

dp = deque([])
b = []
for i in range(n):
    j = bisect_left(dp, a[i])
    if j == 0:
        dp.appendleft(a[i])
    else:
        dp[j-1] = a[i]

print(len(dp))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]

import bisect

bilist = [A[0]]
ans = 0

for a in A[1:]:
    index = bisect.bisect_left(bilist,a)
    if index == 0:
        bisect.insort_left(bilist,a)
    else:
        bilist[index-1] = a


print(len(bilist))

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect
 
n = int(input())
p = [-1*int(input())]
for i in range(n-1):
    now = -1*int(input())
    if now >= p[-1]:
        p.append(now)
    else:
        p[bisect(p,now)] = now
print(len(p))

Submission status: Accepted

Solution code:
import bisect


def main():
    INF = 10 ** 10
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.reverse()
    B = [INF for _ in range(N)]
    for a in A:
        index = bisect.bisect_right(B, a)
        B[index] = a
    ans = 0
    for b in B:
        if b == INF:
            break
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

lst = [a[0]]
for i in range(1, n):
    ai = a[i]
    left = -1
    right = len(lst)
    while left+1 < right:
        mid = (left + right) // 2
        if lst[mid] < ai:
            right = mid
        else:
            left = mid
    if right == len(lst):
        lst.append(ai)
    else:
        lst[right] = ai
print(len(lst))

Submission status: Accepted

Solution code:
from bisect import bisect
N, *A = map(int, open(0).read().split())

mins = []
length = 0
for a in A:
    i = bisect(mins, -a)
    if i >= length:
        mins.append(-a)
        length += 1
    else:
        mins[i] = -a
print(length)

Submission status: Accepted

Solution code:
from bisect import *
def solve():
    ans = 0
    N = int(input())
    A = [-int(input()) for _ in range(N)]
    lis = [A[0]]
    for i in range(1,N):
        if A[i]>=lis[-1]:
            lis.append(A[i])
        else:
            ind = bisect_right(lis,A[i])
            lis[ind] = A[i]
    ans = len(lis)
    return ans
print(solve())

Submission status: Accepted

Solution code:
def binary_search(key):
    bad, good = -1, len(ans)
    while good - bad > 1:
        mid = (bad + good) // 2
        if ans[mid][-1] < key:
            good = mid
        else:
            bad = mid
    return good


N = int(input())
ans = []
for _ in range(N):
    A = int(input())
    idx = binary_search(A)
    if idx == len(ans):
        ans.append([A])
    else:
        ans[idx].append(A)
print(len(ans))

Submission status: Accepted

Solution code:
n=int(input())
m=[]
m.append(int(input()))
count=1
for i in range(n-1):
  k=int(input())
  if k<=m[-1]:
    m.append(k)
    count+=1
  else:
    r=count-1
    l=0
    while l+1<r:
      try1=(r+l)//2
      if m[try1]>=k:
        l=try1
      else:
        r=try1
    if m[l]>=k:
      m[r]=k
    else:
      m[l]=k
print(count)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input())for _ in range(n)]
dp=[2]*(n+1)
from bisect import bisect_left,bisect_right
for i in a:
  dp[bisect_left(dp,-i+1)]=-i
print(dp.index(2))

Submission status: Accepted

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

color_num = [a[0]]
for i in range(1, n):
    if a[i] >= color_num[-1]:
        color_num.append(a[i])
    else:
        temp = bisect.bisect_right(color_num, a[i])
        color_num[temp] = a[i]


print(len(color_num))

Submission status: Accepted

Solution code:
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(input())
    seq = [int(input()) for _ in range(n)][::-1]

    """
    Longest Increasing/Decreasing Subsuquence (LIS, LDS)
    Verified:
        https://atcoder.jp/contests/abc134/tasks/abc134_e
        https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_D
    """


    def longest_subsequence(A: "Array[int]", equals: bool, increasing: bool) -> int:
        """
        Compute the length of LIS or LDS.
        
        Args:
            A ("Array[int]"): a list or tuple to compute.
            equals (bool): permit adjacent numbers in subsequence to equal.
            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 equals else bisect_left
        compare = (lambda x, y: x >= y) if equals else (lambda x, y: x > y)
        if not 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)
    
    print(longest_subsequence(seq,True,True))

    
    




resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right


def read():
    N = int(input().strip())
    A = [int(input().strip()) for _ in range(N)]
    return N, A


def solve(N, A, INF=10**9+1):
    # LIS
    # dp[i]: 長さiの最長増加部分列(A[i]<A[j])のうち、最も小さい数字
    dp = [INF for i in range(N)]
    for i in range(N):
        a = A[N-i-1]
        idx = bisect_right(dp, a)
        dp[idx] = a
    return bisect_right(dp, INF-1)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
import bisect

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

def lis(S):
    from bisect import bisect_right
    L = [S[0]]

    for s in S[1:]:
        if s >= L[-1]:
            L.append(s)
        else:
            L[bisect_right(L, s)] = s
    return len(L)

print(lis(A[::-1]))

Submission status: Accepted

Solution code:
from collections import deque
import bisect

N = int(input())

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

q = deque([A[0]])

for a in A[1:]:
    idx = bisect.bisect_left(q, a)
    if idx == 0:
        q.appendleft(a)
    else:
        q[idx-1] = a

print(len(q))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353


#############
# Main Code #
#############

N = getN()
A = getArray(N)

ans = deque([A[0]])
for i in range(1, N):
    index = bisect_left(ans, A[i])
    if index == 0:
        ans.appendleft(A[i])
    else:
        ans[index - 1] = A[i]

print(len(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = [(-1)*int(input()) for _ in range(n)]
dp = [10**18 for _ in range(n)]

import bisect
def lis(a):
	"""
	param a: list
	return: the length of Longest increasing subsequence
	(be careful that [list] seq is not the LIS, but its length is accurate LIS length.)
	"""
	seq = []
	tmp = 0
	for i in a:
		pos = bisect.bisect_right(seq, i)
		if tmp <= pos:
			seq.append(i)
			tmp += 1
		else:
			seq[pos] = i
	return tmp

print(lis(a))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec = [A[-1]]
    for a in reversed(A[:-1]):
        if a >= vec[-1]:
            vec.append(a)
        else:
            vec[bisect_right(vec, a)] = a

    print(len(vec))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from random import random
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)


class TreapNode:
    _value = None
    _priority = None
    _count = None
    _left = None
    _right = None

    def __init__(self, value):
        self._value = value
        self._priority = random()
        self._count = 1


def treap_rotate_right(n):
    l = n._left
    n._left = l._right
    l._right = n
    return l


def treap_rotate_left(n):
    r = n._right
    n._right = r._left
    r._left = n
    return r


def treap_insert(n, v):
    if n is None:
        return TreapNode(v)
    if n._value == v:
        n._count += 1
        return n
    if n._value > v:
        n._left = treap_insert(n._left, v)
        if n._priority > n._left._priority:
            n = treap_rotate_right(n)
    else:
        n._right = treap_insert(n._right, v)
        if n._priority > n._right._priority:
            n = treap_rotate_left(n)
    return n


def treap_delete(n, v):
    if n is None:
        raise Exception('no nodes')
    if n._value > v:
        n._left = treap_delete(n._left, v)
        return n
    if n._value < v:
        n._right = treap_delete(n._right, v)
        return n

    # n._value == v
    if n._count > 1:
        n._count -= 1
        return n

    if n._left is None and n._right is None:
        return None

    if n._left is None:
        n = treap_rotate_left(n)
    elif n._right is None:
        n = treap_rotate_right(n)
    else:
        # n._left is not None and n._right is not None
        if n._left._priority < n._right._priority:
            n = treap_rotate_right(n)
        else:
            n = treap_rotate_left(n)
    return treap_delete(n, v)


def treap_size(n):
    if n is None:
        return 0
    return n._count + treap_size(n._left) + treap_size(n._right)


def treap_str(n):
    if n is None:
        return ""
    result = []
    if n._left is not None:
        result.append(treap_str(n._left))
    result.append("%d:%d" % (n._value, n._count))
    if n._right is not None:
        result.append(treap_str(n._right))
    return ' '.join(result)


def treap_search(n, v):
    # v 未満で最大のノードを検索する. v 未満のノードがなければ None を返す
    if n is None:
        return None
    if n._value >= v:
        if n._left is None:
            return None
        return treap_search(n._left, v)
    # n._value < v
    if n._right is None:
        return n
    r = treap_search(n._right, v)
    if r is None:
        return n
    return r


class Treap:
    _root = None
    _size = 0

    def insert(self, v):
        self._root = treap_insert(self._root, v)
        self._size += 1

    def delete(self, v):
        self._root = treap_delete(self._root, v)
        self._size -= 1

    def __len__(self):
        return self._size

    def __str__(self):
        return treap_str(self._root)

    def search(self, v):
        return treap_search(self._root, v)


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

t = Treap()
for a in A:
    n = t.search(a)
    if n is not None:
        t.delete(n._value)
    t.insert(a)
print(len(t))

Submission status: Accepted

Solution code:
from bisect import bisect_right

N = int(input())
A = [int(input()) for i in range(0,N,1)]

maxs = []#今まで塗ってきた各色の最大値 の負の値を入れるといろいろ楽なんですよまあ見ててよ

for i in range(0,N,1):
    to_insert = bisect_right(maxs,-A[i])
    if len(maxs)==0:#最初の一回
        maxs.insert(0,-A[i])
    else:
        if to_insert < len(maxs):
            maxs[to_insert]=-A[i]
        else:
            maxs.append(-A[i])

print(len(maxs))

Submission status: Accepted

Solution code:
# ABC134E

import sys
input=sys.stdin.readline

def bisectR(ite,x):
    st=-1
    en=len(ite)
    while(en-st>1):
        mid=(en+st)//2
        if ite[mid]<x:
            en=mid
        else:
            st=mid
    return en

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    
    lbds=[A[0]]
    for i in range(1,N):
        if lbds[-1]>=A[i]:
            lbds+=[A[i]]
        else:
            x=bisectR(lbds,A[i])
            lbds[x]=A[i]
    print(len(lbds))
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from bisect import bisect_right
lis = [1]
for a in As:
    if a>=lis[-1]:
        lis.append(a)
    else:
        lis[bisect_right(lis, a)] = a

print(len(lis))

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
  temp = int(input())
  A.append(temp)
#print(A)
L = [A[0]]
for i in range(1,N):
  if L[-1] >= A[i]:
    L.append(A[i])
  else:
    if L[0] < A[i]:
      L[0] = A[i]
    else:
      s = len(L)
      ok = s
      ng = 0
      while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if L[mid] < A[i]:
          ok = mid
        else:
          ng = mid
      L[ok] = A[i]
  #print(L)
ans = len(L)
print(ans)

Submission status: Accepted

Solution code:
import sys
# from collections import defaultdict, deque
# import math
# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007
def solve():
    n = getN()
    dp = [-INF]
    for i in range(n):
        num = getN()
        num = -num
        if num >= dp[-1]:
            dp.append(num)
        else:
            idx = bisect_right(dp, num)
            dp[idx] = num


    print(len(dp) - 1)
    return

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left
from bisect import bisect_right

INF = float("inf")


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

    dp = [INF]*N
    for i in range(N):
        j = bisect_right(dp, -A[i])
        dp[j] = -A[i]

    print(bisect_left(dp, INF))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_right

INF = float("inf")


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

    dp = [INF]*N
    for i in range(N):
        j = bisect_right(dp, -A[i])
        dp[j] = -A[i]

    print(sum([1 for d in dp if d < INF]))
    # print(dp)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def bisect_right_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番右側のidx+1となる。
    '''
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

def main():
  N = int(input())
  ans = 1
  lis_min = [int(input())]
  for i in range(N-1):
    a = int(input())
    index = bisect_right_reverse(lis_min, a)
    if index != len(lis_min):
      lis_min[index] = a
    else:
      ans += 1
      lis_min.append(a)
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from random import random
from sys import setrecursionlimit

setrecursionlimit(10 ** 5)


class TreapNode:
    _value = None
    _priority = None
    _count = None
    _left = None
    _right = None

    def __init__(self, value):
        self._value = value
        self._priority = random()
        self._count = 1


def treap_rotate_right(n):
    l = n._left
    n._left = l._right
    l._right = n
    return l


def treap_rotate_left(n):
    r = n._right
    n._right = r._left
    r._left = n
    return r


def treap_insert(n, v):
    if n is None:
        return TreapNode(v)
    if n._value == v:
        n._count += 1
        return n
    if n._value > v:
        n._left = treap_insert(n._left, v)
        if n._priority > n._left._priority:
            n = treap_rotate_right(n)
    else:
        n._right = treap_insert(n._right, v)
        if n._priority > n._right._priority:
            n = treap_rotate_left(n)
    return n


def treap_delete(n, v):
    if n is None:
        raise Exception('no nodes')
    if n._value > v:
        n._left = treap_delete(n._left, v)
        return n
    if n._value < v:
        n._right = treap_delete(n._right, v)
        return n

    # n._value == v
    if n._count > 1:
        n._count -= 1
        return n

    if n._left is None and n._right is None:
        return None

    if n._left is None:
        n = treap_rotate_left(n)
    elif n._right is None:
        n = treap_rotate_right(n)
    else:
        # n._left is not None and n._right is not None
        if n._left._priority < n._right._priority:
            n = treap_rotate_right(n)
        else:
            n = treap_rotate_left(n)
    return treap_delete(n, v)


def treap_size(n):
    if n is None:
        return 0
    return n._count + treap_size(n._left) + treap_size(n._right)


def treap_str(n):
    if n is None:
        return ""
    result = []
    if n._left is not None:
        result.append(treap_str(n._left))
    result.append("%d:%d" % (n._value, n._count))
    if n._right is not None:
        result.append(treap_str(n._right))
    return ' '.join(result)


def treap_search(n, v):
    # v 未満で最大のノードを検索する. v 未満のノードがなければ None を返す
    if n is None:
        return None
    if n._value >= v:
        if n._left is None:
            return None
        return treap_search(n._left, v)
    # n._value < v
    if n._right is None:
        return n
    r = treap_search(n._right, v)
    if r is None:
        return n
    return r


class Treap:
    _root = None
    _size = 0

    def insert(self, v):
        self._root = treap_insert(self._root, v)
        self._size += 1

    def delete(self, v):
        self._root = treap_delete(self._root, v)
        self._size -= 1

    def __len__(self):
        return self._size

    def __str__(self):
        return treap_str(self._root)

    def search(self, v):
        return treap_search(self._root, v)


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

t = Treap()
for a in A:
    n = t.search(a)
    if n is not None:
        t.delete(n._value)
    t.insert(a)
print(len(t))

Submission status: Accepted

Solution code:
import bisect
# from collections import deque
# from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt
 
n = int(input())
li = [int(input()) for i in range(n)]
li = [-x for x in li]

X = []
X.append(li[0])

for i in range(1,n):
    idx = bisect.bisect_right(X,li[i])
    if idx==len(X):
        X.append(li[i])
    else:
        X[idx] = li[i]

print(len(X))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    vec = [INF] * N
    for a in reversed(A):
        vec[bisect_right(vec, a)] = a

    try:
        print(vec.index(INF))
    except:
        print(N)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    vec = [INF] * N
    for a in reversed(A):
        vec[bisect_right(vec, a)] = a

    print(N - vec.count(INF))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    vec = [A[-1]]
    for a in reversed(A[:-1]):
        if a >= vec[-1]:
            vec.append(a)
        else:
            vec[bisect_right(vec, a)] = a

    print(len(vec))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import bisect
import sys
sys.setrecursionlimit(10**9)


def main():
    N = int(input())
    X = deque()

    for _ in range(N):
        a = int(input())
        j = bisect.bisect_left(X,a)

        if j == 0:
            X.appendleft(a)
        else:
            X[j-1] = a


    print(len(X))


if __name__ == "__main__":
  main()

Submission status: Accepted

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

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

LIS = [-1] * N
LIS[-1] = seq[0]
#print(LIS)
for i in range(1, len(seq)):
    LIS[bisect.bisect_left(LIS, seq[i]) - 1] = seq[i]
    #print(LIS)
#print(LIS)
c = LIS.count(-1)
print(len(LIS) - c)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = []

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

stack = [a[0]]

for i in range(1, n):
    index = bisect.bisect_right(stack, a[i])
    if index == len(stack):
        stack.append(a[i])
    else:
        stack[index] = a[i]

print(len(stack))

Submission status: Accepted

Solution code:
import sys
import bisect

input = lambda: sys.stdin.readline().rstrip()

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


def solve():

    LIS = [A[0]]
    for i in range(1, N):

        if A[i] >= LIS[-1]:
            LIS.append(A[i])
        else:
            LIS[bisect.bisect_right(LIS, A[i])] = A[i]

    ans = len(LIS)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc134/tasks/abc134_e　

from bisect import bisect_left
from collections import *

N = int(input())

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

LIS = deque([A[0]])
cnt = 0

for a in A[1:]:
    if a <= LIS[0]:
        LIS.appendleft(a)
    else:
        ind = bisect_left(LIS, a) -1
        LIS[ind] = a

print(len(LIS))

Submission status: Accepted

Solution code:
n=int(input())
a=[-int(input()) for i in range(n)]
from bisect import bisect_right
l=[]
for aa in a:
  idx=bisect_right(l,aa)
  if idx==len(l):
    l.append(aa)
  else:
    l[idx]=aa
print(len(l))

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

li = list()
for e in a:
    i = bisect_right(li, e)
    if i == len(li):
        li.append(e)
    else:
        li[i] = e

ans = len(li)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

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

dq = deque()
for e in a:
    i = bisect_left(dq, e)
    if i == 0:
        dq.appendleft(e)
    else:
        dq[i-1] = e

ans = len(dq)
print(ans)

Submission status: Accepted

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

import bisect
#a=[0,2,3,4,67,8]
#a.sort()
#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

color=[1]
lencolor=1
for aa in a:
    aa=-1*aa
    i=bisect.bisect_right(color, aa)
    if i==lencolor:
        color.append(aa)
        lencolor+=1
        #print("insert")
    else:
        color[i]=aa
        #print("update")
    #print(color,aa) 
print(lencolor)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
A = A[::-1]
S = [A[0]]
c = 1
for i in range(1, N):
    t = A[i]
    if t >= S[-1]:
        S.append(t)
        c += 1
    else:
        p = bisect.bisect_right(S, t)
        S[p] = t
print(c)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
ans = 0
X = [int(input())for _ in range(N)]
A = []
for a in X[::-1]:
    if len(A) == 0:
        A.append(a)
    elif A[-1] <= a:
        A.append(a)
    else:
        i = bisect.bisect_right(A, a)
        A[i] = a

print(len(A))

Submission status: Accepted

Solution code:
from collections import deque
import bisect

def main():
    N = int(input())
    l = deque([])

    for i in range(N):
        a = int(input())
        if len(l) == 0 or a <= l[0]:
            l.appendleft(a)
        else:
            ind = bisect.bisect_left(l, a)
            l[ind-1] = a

    print(len(l))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
from collections import deque

n = int(input())
#c = []
c = deque([])
for i in range(n):
    a = int(input())
    if i == 0:
        c.append(a)
    else:
        ind = bisect.bisect_left(c,a)
        if ind > 0:
            c[ind-1] = a
        else:
            c.appendleft(a)

print(len(c))

Submission status: Accepted

Solution code:
from bisect import bisect_right
n = int(input())
a_list = []
for i in range(n):
    a = int(input())
    a_list.append(a)
a_list.reverse()
l_list = [a_list[0]]
for i in range(1, n):
    a = a_list[i]
    if l_list[-1] <= a:
        l_list.append(a)
    else:
        index = bisect_right(l_list, a)
        l_list[index] = a
print(len(l_list))

Submission status: Accepted

Solution code:
import bisect
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]
c = deque()
c.append(A[0])
for i in range(1, N):
    j = bisect.bisect_left(c, A[i])
    if j == 0:
        c.appendleft(A[i])
    else:
        c[j-1] = A[i]
print(len(c))

Submission status: Accepted

Solution code:
import bisect
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]
c = deque()
c.append(A[0])
for i in range(1, N):
    j = bisect.bisect_right(c, A[i]-1)
    if j == 0:
        c.appendleft(A[i])
    else:
        c[j-1] = A[i]
print(len(c))

Submission status: Accepted

Solution code:
import bisect
N=int(input())
A=[]
ans=0
for i in range(N):
    a=int(input())
    A.append(a)
cl=[A[-1]]
ans=1
for i in range(N-1)[::-1]:
    a=A[i]
    if a>=cl[-1]:
        cl.append(a)
        ans+=1
    else:
        b=bisect.bisect_right(cl,a)
        cl[b]=a
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    import bisect

    read = sys.stdin.buffer.read
    bisect_right = bisect.bisect_right

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

    dp = [A[-1]]
    for a in reversed(A[:-1]):
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a

    print(len(dp))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    dp = [A.pop()]
    for a in reversed(A):
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a

    print(len(dp))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    dp = [A[-1]]
    for a in reversed(A[:-1]):
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a

    print(len(dp))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    A.reverse()

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

    print(len(dp))
    return


if __name__ == '__main__':
    main()