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:
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 v == n._value:
        n._count += 1
        return n
    if v < n._value:
        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:
        return None
    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):
    # x 未満で最大のノードを検索する. n 未満のノードがなければ nil を返す
    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

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

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

    def __len__(self):
        return treap_size(self._root)

    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 random import random
from sys import setrecursionlimit

setrecursionlimit(3 * 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 v == n._value:
        n._count += 1
        return n
    if v < n._value:
        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:
        return None
    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):
    # x 未満で最大のノードを検索する. n 未満のノードがなければ nil を返す
    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

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

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

    def __len__(self):
        return treap_size(self._root)

    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 sys import stdin, setrecursionlimit
from bisect import bisect_right

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


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

    for a in A[1:]:
        if a <= -B[-1]:
            B.append(-a)
        else:
            B[bisect_right(B, -a)] = -a

    print(len(B))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from bisect import bisect_left
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


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

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

    print(len(B))


if __name__ == '__main__':
    main()

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_right, bisect_left
def resolve():
    N = int(input())
    A = [int(input()) for _ in range(N)][::-1]

    dp = [INF]*(N+1)
    for a in A:
        ind = bisect_right(dp, a)
        dp[ind] = a

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
from collections import deque
from bisect import bisect_left

N = INT()
A = []

for _ in range(N):
    A.append(INT())

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

print(len(t))

Submission status: Accepted

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

import bisect

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

A.reverse()
INF = float('inf')
dp = [INF for _ in range(N)]

for a in A:
    target_index = bisect.bisect_right(dp, a)
    # print(a, target_index)
    dp[target_index] = a

# print(dp)
print(bisect.bisect_left(dp, INF))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = [int(input()) for i in range(n)]
ans = 0
color = [a[n-1]]
for i in range(n-2,-1,-1):
    if a[i]>=color[-1]:
        color.append(a[i])
    else:
        x = bisect.bisect_right(color,a[i])
        color[x] = a[i]
print(len(color))

Submission status: Accepted

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

t = [A[0]]
for a in A[1:]:
    if t[-1] >= a:
        t.append(a)
        continue
    ok = len(t) - 1
    ng = -1
    while ok - ng > 1:
        m = (ok + ng) // 2
        if t[m] < a:
            ok = m
        else:
            ng = m
    t[ok] = a
print(len(t))

Submission status: Accepted

Solution code:

from collections import deque

n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
l=deque([a[0]])
for i in range(1,n):
    if l[0]>=a[i]:
        l.appendleft(a[i])
    elif l[-1]<a[i]:
        l[-1]=a[i]
    else:
        p=0
        q=len(l)-1
        while q-p!=1:
            if l[(p+q)//2]>=a[i]:
                q=(p+q)//2
            else:
                p=(p+q)//2
        l[p]=a[i]
print(len(l))

Submission status: Accepted

Solution code:
n = int(input())

colors = []

for i in range(n):
  a = int(input())
  if i == 0:
    colors.append(a)
    continue
  if colors[-1] >= a:
    colors.append(a)
  elif a > colors[0]:
    colors[0] = a
  else:
    l, r = 0, len(colors)
    while r-l > 1:
      k = (r+l)//2
      if a > colors[k]:
        r = k
      else:
        l = k
    if a > colors[l]:
      colors[l] = a
    else:
      colors[r] = a

print(len(colors))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

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

    print(len(color))


if __name__ == "__main__":
    main()

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):
    ans = 0
    lis = []
    for i in range(N):
        ind = bisect_right(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 sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = []
for i in range(n):
  a = int(input())
  chk.append(a)
  
from bisect import bisect_left,insort_left
from collections import deque
ans = 0

c = deque([])
for j in chk:
  if i == 0:
    c.append(j)
  else:
    ind = bisect_left(c,j)
    if ind == 0:
      ans += 1
      c.appendleft(j)
    else:
      c[ind-1] = (j)
      
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = []
for i in range(n):
  a = int(input())
  chk.append((i,a))
  
from bisect import bisect_left,insort_left
from collections import deque
ans = 1

c = deque([])
for j in chk:
  i,a = j
  if i == 0:
    c.append((a,n-i))
  else:
    ind = bisect_left(c,(a,n-i))
    if ind == 0:
      ans += 1
      c.appendleft((a,n-i))
    else:
      c[ind-1] = (a,n-i)
      
print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
LIS = [-1 * int(input())]
for _ in range(N-1):
    A = -1 * int(input())
    if A >= LIS[-1]:
        LIS.append(A)
    else:
        LIS[bisect.bisect_right(LIS, A)] = A

print(len(LIS))

Submission status: Accepted

Solution code:
import bisect
from collections import deque
N = int(input())
nums = [int(input()) for _ in range(N)]
# i<jで、 AiとAjが同じ色で塗られている場合、Ai < Ajが成り立つ.
# その際に、色の最小数をだす。
LIS = deque([nums[0]])
count = 0
for index, num in enumerate(nums):
    if index == 0:
        continue
    if num <= LIS[0]:
        LIS.appendleft(num)
    else:
        insert_index = bisect.bisect_left(LIS, num)
        LIS[insert_index - 1] = num
print(len(LIS))

Submission status: Accepted

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

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

def solve(N: int):
    tokens = iterate_tokens()
    colors_top = []
    for i in range(N):
        new = int(next(tokens))
        if colors_top:
            b = bisect.bisect_right(colors_top, -new)
            if b == len(colors_top):
                colors_top.append(-new)
            else:
                colors_top[b] = -new
        else:
            colors_top.append(-new)
    print(len(colors_top))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from collections import deque
import bisect


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

d = deque()

for a in A:
    p = bisect.bisect_left(d, a)
    if p == 0:
        d.appendleft(a)
        continue
    d[p-1] = a

print(len(d))

Submission status: Accepted

Solution code:

import heapq
from collections import defaultdict, deque
# from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))
# ----------

N = ii()
A = []
for i in range(N):
    A.append(ii())

d = deque()

for a in A:
    p = bisect.bisect_left(d, a)
    if p == 0:
        d.appendleft(a)
        continue
    d[p-1] = a

print(len(d))

Submission status: Accepted

Solution code:
n=int(input())
A=[int(input()) for i in range(n)]
l=[-A[0],1]#-にして小さい順から並ぶようにする
from bisect import *
for a in A[1:]:
    idx=bisect_left(l,-a+1)
    p=-l[idx]
    if p==-1:
        l[-1]=-a
        l.append(1)
    else:
        l[idx]=-a
print(len(l)-1)

Submission status: Accepted

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

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

print(len(que))
#print(que)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#import numpy as np
import bisect
from collections import deque

def main():
	n=II()
	A=[II() for _ in range(n)]

	Q=deque([A[0]])
	#print(Q)
	for i in range(1,n):
		if A[i]<=Q[0]:
			Q.appendleft(A[i])
		else:
			a=bisect.bisect_left(Q,A[i])
			Q[a-1]=A[i]
	print(len(Q))








if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import bisect

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


colors = []
for i in reversed(range(N)):
    if i == N-1:
        colors.append(A[i])
    else:
        if A[i] >= colors[-1]:
            colors.append(A[i])
        # 積む色がある場合
        else:
            idx = bisect.bisect_right(colors, A[i])
            colors[idx] = A[i]


print(len(colors))

Submission status: Accepted

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
infi = 10 ** 20

# 長さがi+1のときの最長部分増加列の末尾の最小値。
n, *A = map(int, read().split())
LIS = deque([10 ** 10])
for a in A:
    a *= -1
    pos1 = bisect_left(LIS, a)
    pos2 = bisect_right(LIS, a)
    if LIS[-1] <= a:
        LIS.append(a)
    else:
        if LIS[pos1] == a:
            LIS[pos2] = a
        else:
            LIS[pos1] = a

print(len(LIS))

Submission status: Accepted

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

INF = float('inf')

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

def getLenLNDS(As):
    dp = [-INF]
    for A in As:
        if dp[-1] <= A:
            dp.append(A)
        else:
            i = bisect_right(dp, A)
            dp[i] = A
    return len(dp)-1

ans = getLenLNDS(As)

print(ans)

Submission status: Accepted

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

print(len(b))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    A=[-int(input()) for i in range(N)]
    dp=[INF]*(N+2)
    dp[0]=-INF
    for i in range(N):
        dp[bisect_right(dp,A[i])]=A[i]
    for i in range(N+2):
        if dp[i]==INF:
            print(i-1)
            exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    

    def reverse_bisect(L, key):
        """
        L は単調減少
        key 未満となる最初の index を返す
        - left は常に key 未満の条件を満たさない
        - right は常に key 未満の条件を満たす
        - right - left で表される区間幅が 1 になるまで狭める。right が答えになる。
        """
        left = -1
        right = len(L)
        while right - left > 1:
            mid = left + (right - left) // 2
            if L[mid] < key:
                right = mid
            else:
                left = mid
        return right

    
    # 広義最大減少部分列の長さが答え
    n = ii()
    L = [ii() for _ in range(n)]
    # dp[i] には長さ i+1 の広義減少部分列を作った時、末尾の値が最大となるものの値のメモがなされる
    # dp は広義単調減少
    dp = [-float('inf')] * n
    for elm in L:
        insert_ind = reverse_bisect(dp, elm)
        dp[insert_ind] = elm

    prev = -1
    for i, tail_max in enumerate(dp):
        if tail_max == -float('inf'):
            # dp[prev] が メモられてる最後の要素。長さ prev + 1 の広義減少部分列まで作成可能である。
            break
        prev = i
    print(prev + 1)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)][::-1]
def LIS(L):
  from bisect import bisect
  seq=[]
  for i in L:
    pos=bisect(seq,i)
    if len(seq)<=pos:
      seq.append(i)
    else:
      seq[pos]=i
  return len(seq)
print(LIS(A))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import bisect
from collections import deque

def main():
    N = int(input())
    INF = 10**10
    col = deque([INF])
    for _ in range(N):
        num = int(input())
        ind = bisect.bisect_left(col,num)
        if ind == 0:
            col.appendleft(num)
        else:
            col[ind-1] = num
    
    print(len(col)-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
N=int(input())

alist=[]
for i in range(N):
  alist.append(int(input()))
#print(alist)

color_list=[alist.pop()]
for i in reversed(range(N-1)):
  a=alist[i]
  if a>=color_list[-1]:
    #insert to tail
    color_list.append(a)
  else:
    #replace
    pos=bisect.bisect(color_list,a)
    color_list[pos]=a
  #print(color_list)
  
print(len(color_list))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from bisect import bisect_left, bisect_right

n = int(readline())
a = [int(readline()) for _ in range(n)]
inf = float('inf')
memo = [inf] * n
for aa in a[::-1]:
    memo[bisect_right(memo, aa)] = aa
print(bisect_left(memo, inf))

Submission status: Accepted

Solution code:
from bisect import bisect_right,bisect_left
n=int(input())
a=[int(input()) for _ in range(n)]
INF=float('INF')
l=[INF]*n
for i in a[::-1]:
    l[bisect_right(l,i)]=i
print(bisect_left(l,INF))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
import bisect

INF = 10 ** 18
N = int(input())
A = [10 ** 10 - int(input()) for _ in range(N)]  # 逆順にしておく

# 最長単調減少列：狭義

dp = [INF] * (N + 1)  # 長さ、その長さの末端としてありうる最大値

for a in A:
    idx = bisect.bisect_right(dp, a)
    dp[idx] = a

answer = bisect.bisect_left(dp, INF)
print(answer)

Submission status: Accepted

Solution code:
import bisect
from collections import deque
n = int(input())
color = [-1]*n

for i in range(n):
    a = int(input())
    color[bisect.bisect_left(color,a) - 1] = a

ans = n - bisect.bisect_right(color,-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left
from collections import deque

def main():
    N = int(input())
    counter = deque([])
    for _ in range(N):
        a = int(input())
        ind = bisect_left(counter, a)
        if ind == 0:
            counter.appendleft(a)
        else:
            counter[ind-1] = a
    print(len(counter))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = [int(input()) for i in range(n)]
dp = [-inf] * (10**5+10);dp[-1] = inf
for ai in A:
  dp[bisect.bisect_left(dp,ai)-1] = ai
for di in dp:
  if di != -inf:ans += 1
print(ans - 1)

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = A[::-1]
INF = int(1e+9 + 10)
lis = [INF] * N
for n in range(N):
    i = bisect.bisect(lis, A[n])    
    lis[i] = A[n]
print (bisect.bisect_left(lis, INF))

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = A[::-1]
INF = int(1e+9 + 10)
lis = [INF]* (N+1)
lis[0] = -1
for n in range(N):
    i = bisect.bisect(lis, A[n])    
    lis[i] = A[n]
print (bisect.bisect_left(lis, INF) - 1)

Submission status: Accepted

Solution code:
from bisect import bisect_right

N = int(input())
A = [int(input()) for _ in range(N)]
INF = 10**18

dp = [INF] * N
for a in A:
    dp[bisect_right(dp, -a)] = -a
ans = N - dp.count(INF)
print(ans)