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 bisect import bisect_left
N = int(input())
memo = [-1]*N
for _ in range(N):
    a = int(input())
    idx = bisect_left(memo,a)-1
    memo[idx] = a

print(N-memo.count(-1))

Submission status: Accepted

Solution code:
from bisect import bisect
N = int(input())
dp = [1]*N
for _ in range(N):
  a=-int(input())
  n=bisect(dp,a)
  dp[n]=a
print(sum(1 for i in dp if i <= 0))

Submission status: Accepted

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

LIS = deque()  # LISの中身は、LISの最小の数字を保持する
LIS.append(a[0])
for i in range(1, n):
    idx = bisect_left(LIS, a[i])
    if idx == 0:
        LIS.appendleft(a[i])
    else:
        LIS[idx-1] = a[i]
print(len(LIS))

Submission status: Accepted

Solution code:
import bisect, collections

n = int(input())
num = collections.deque([])
for i in range(n):
    a = int(input())
    temp = bisect.bisect_left(num, a)
    if temp == 0:
        num.appendleft(a)
    else:
        num[temp - 1] = a
print(len(num))

Submission status: Accepted

Solution code:
from bisect import bisect, bisect_left

N = int(input())
dp = [1]*N

for _ in range(N):
  a = -int(input())
  n = bisect(dp, a)
  dp[n] = a

print(sum( 1 for i in dp if i <= 0 ))

Submission status: Accepted

Solution code:
N = int(input())
seq = [int(input()) for _ in range(N)]
from collections import deque
import bisect
LIS = deque([seq[0]])
for i in range(1,len(seq)):
    if seq[i] <= LIS[0]:
        LIS.appendleft(seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i])-1] = seq[i]

print(len(LIS))

Submission status: Accepted

Solution code:
N = int(input())
seq = [int(input()) for _ in range(N)]
from collections import deque
import bisect
LIS = deque([seq[0]])
for i in range(1,len(seq)):
    if seq[i] <= LIS[0]:
        LIS.appendleft(seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i])-1] = seq[i]

print(len(LIS))

Submission status: Accepted

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

X = deque([])

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

Submission status: Accepted

Solution code:
from bisect import bisect_right


def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    a.reverse()
    lis = [a[0]]
    for i in range(1, n):
        if a[i] >= lis[-1]:
            lis.append(a[i])
        else:
            lis[bisect_right(lis, a[i])] = a[i]
    print(len(lis))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
c=[]
hc=0
for i in range(n):
  a=int(input())
  l,r=-1,hc
  while r-l!=1:
    t=(l+r)//2
    if c[t]<a:
      r=t
    else:
      l=t
  if r==hc:
    c.append(a)
    hc+=1
  else:
    c[r]=a
print(hc)

Submission status: Accepted

Solution code:
from sys import *
from bisect import *

n = int(input())
a = list(map(int, stdin.readlines()))

dp = [1]
for j in a:
    j *= -1
    i = bisect(dp, j)
    if i < len(dp):
        dp[i] = j
    else:
        dp.append(j)
print(len(dp))

Submission status: Accepted

Solution code:
import bisect
N= int(input())
dp = [-1]*N
cnt =0
for i in range(N):
    a = int(input())
    idx = bisect.bisect_left(dp,a)
    dp[idx-1]=a
print(len(dp[bisect.bisect_left(dp,0):]))

Submission status: Accepted

Solution code:
import bisect
N= int(input())
dp = [-1]*N
cnt =0
for _ in range(N):
    a = int(input())
    idx = bisect.bisect_left(dp,a)
    dp[idx-1]=a
print(len(dp[bisect.bisect_left(dp,0):]))

Submission status: Accepted

Solution code:
from bisect import*
INF=10**18
n=int(input())
dp=[-1]*n
for _ in range(n):
  i=int(input())
  dp[bisect_left(dp,i)-1]=i
print(sum([i>=0 for i in dp]))

Submission status: Accepted

Solution code:
from collections import deque
import bisect
N=int(input())
L=deque()
for i in range(N):
  s=int(input())
  if i==0:
    L.append(s)
  else:
    if s<=L[0]:
      L.appendleft(s)
    else:
      L[bisect.bisect(L,s-1)-1]=s
print(len(L))

Submission status: Accepted

Solution code:
from bisect import bisect_right
def main():
    N = int(input())
    min_a = 10**9 + 1
    values = []
    ans = 0
    for i in range(N):
        tmp = -int(input())
        idx = bisect_right(values, tmp)
        if idx != len(values):
            values[idx] = tmp
        else:
            values.append(tmp)
            ans += 1

    print(ans)








main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N = I()
    D = [float('inf')]*N
    for i in range(N):
        num = -I()
        index = bisect_right(D, num)
        D[index] = num

    res = 0
    for i in D:
        if i != float('inf'):
            res+=1
        else:
            break
    print(res)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
def solve(A,n):
    import bisect
    dp = [float('inf')] * n
    for i in range(n-1,-1,-1):
        k = bisect.bisect_right(dp, A[i])
        dp[k] = A[i]
    ans = 0
    for a in dp:
        if a != float('inf'):
            ans += 1
        else:
            break
    return ans
print(solve(A,N))

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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

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

print(len(dq))

Submission status: Accepted

Solution code:
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()
 
 
def main():
    n = int(input())
    A=[0]*n
    for i in range(1,n+1):
        A[-i]=int(input())
    inf=10**10    
    dp=[0]
    for AA in A:
        if dp[-1]<=AA:
            dp.append(AA)
        else:
            bis=bisect.bisect_right(dp, AA)
            dp[bis]=AA #n以下の個数を数える
    print(len(dp)-1)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7


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

print(len(LIS))

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]
dp = [-1] * N
dp[N-1] = A[0]

ans = 0
for i in range(1, N):
    target_index = bisect.bisect_left(dp, A[i])
    dp[target_index-1] = A[i]

print(N - dp.count(-1))

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    ans = [-int(ipt())]
    for i in range(n-1):
        a = -int(ipt())
        if a >= ans[-1]:
            ans.append(a)
        else:
            ans[bisect.bisect_right(ans,a)] = a
#        print(ans)
    print(len(ans))

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys, copy, itertools,bisect
input = sys.stdin.readline
  
n = int(input())
A = []
for i in range(n):
  a = int(input())
  A.append(a)
  
A.reverse() #逆順に変更

LDS =[A[0]] #初期値導入
#LDS=Longest Decreasing Subsequence
 
for i in range(1,n):
  x = A[i]
  index = bisect.bisect_right(LDS,x) #二分探索、right:同値は追加
  if index == len(LDS):
    LDS.append(x) #単純に後ろに追加する
  else:
    LDS[index]  = x
    #配列LDSの中で二分探索し、A[i]より大きい最小の位置を求め、その数字を置き換える  


#print(LDS)
print(len(LDS))

Submission status: Accepted

Solution code:
from collections import deque
import sys, copy, itertools,bisect
input = sys.stdin.readline

def isOK(LIST, index, key):  #key以上で最大のindexを返す
  if LIST[index] <= key:
    return True
  else:
    return False

def meguru_binary_search(LIST, key):
  ng = -1
  ok = len(LIST)
  while abs(ok-ng) > 1:
    mid = (ok + ng) //2 #"//"は切り捨て除算
    if isOK(LIST, mid, key):
      ok = mid
    else:
      ng = mid
  return ok  
  

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

LDS =[A[-1]] #初期値導入
#LDS=Longest Decreasing Subsequence
 
for i in range(2,n+1):
  x = A[-i]
  index = bisect.bisect_right(LDS,x)
  if index == len(LDS):
    LDS.append(x) #単純に後ろに追加する
  else:
    LDS[index]  = x
    #配列LDSの中で二分探索し、A[i]より小さい最小の位置を求め、その数字を置き換える  

#print(LDS)
print(len(LDS))

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる

        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき

            self.cnt=0#要素数を持っておくか
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

            self.cnt+=1#追加

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

            self.cnt-=1

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #x未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            self.cnt-=1
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)


        def all(self):
            print(self.layer1)
            print(self.layer0)

        def len(self):
            return self.cnt

    ##############################

    N=I()


        
    ssl=SquareSkipList(square=2000)
    ssl.add(-1)
    
    #与えられた値未満の最大値を探してそれを引き上げる，なければ新しく作る
    for i in range(N):
        a=I()
        b=ssl.search_lower(a)
        if b==-1:#ない場合
            pass
        else:
            ssl.remove(b)
        ssl.add(a)
        
        
    ans=ssl.len()-1
    print(ans)
            
        
    
        
    



main()

Submission status: Accepted

Solution code:
import bisect

N = int(input())
a = [int(input()) for _ in range(N)]
b = [a[-1]]
for i in range(2, N+1):
    x = a[-i]
    index = bisect.bisect_right(b, x)
    if index == len(b):
        b.append(x)
    else:
        b[index] = x
print(len(b))

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
d=[]
a=(int(input()))*-1
d.append(a)
ans=1
for i in range(n-1):
    a=-1*(int(input()))
    ind=bisect.bisect_right(d,a)
    l=len(d)
    if ind==l:
        d.append(a)
        ans+=1
    else:
        d[ind]=a
print(ans)

Submission status: Accepted

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

N = int(input())
A = [int(input()) for _ in range(N)]
INF = 10**18
arr = deque([])
for a in A:
    l, r = -1, len(arr)
    while (r-l) > 1:
        mid = (r+l)//2
        if arr[mid] < a:
            l = mid
        else:
            r = mid
    if l == -1:
        arr.appendleft(a)
    else:
        arr[l] = a
print(len(arr))

Submission status: Accepted

Solution code:
from bisect import bisect_right


N, *A = map(int, open(0).read().split())
A = [-a for a in A]
q = []
for a in A:
    idx = bisect_right(q, a)
    if idx == len(q):
        q.append(a)
    else:
        q[idx] = 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 = 10 ** 9 + 7


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

N = getN()
A = getArray(N)

def lis(A):
    L = deque([A[0]])
    for a in A[1:]:
        # Lのどの数より小さくければ
        # 繋げられるものがない
        if a <= L[0]:
            L.appendleft(a)
        else:
            # L[bisect_left(L, a) - 1]
            # Lの中のa未満の数字のうちの最大値
            L[bisect_left(L, a) - 1] = a
    return len(L)

print(lis(A))

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import bisect
from collections import deque

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

	Q=deque()
	Q.append(A[0])

	for i in A[1:]:
		x=bisect.bisect_left(Q,i)
		if x==0:
			Q.appendleft(i)
		else:
			Q[x-1]=i
	print(len(Q))





















if __name__ == "__main__":
	main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
A = [int(input()) for _ in range(N)]
L = [-1] * N
for a in A:
    idx = bisect_left(L, a)
    L[idx-1] = a
print(N - L.count(-1))

Submission status: Accepted

Solution code:
import bisect
n, *a = map(int, open(0).read().split())
a = a[::-1]
INF = 1 << 30
dp = [INF] * (n + 1)

for e in a:
    dp[bisect.bisect_right(dp, e)] = e
print(bisect.bisect_left(dp, INF))

Submission status: Accepted

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

A.reverse()

import bisect
B = [10**18]
for a in A:
    i = bisect.bisect_right(B, a)
    if 0 <= i < len(B):
        B[i] = a
    else:
        B.append(a)
print(len(B))

Submission status: Accepted

Solution code:
import heapq
from bisect import bisect_left, bisect_right

n = int(input())
a = int(input())
q = [a*(-1)]
# ans = 1

for _ in range(n-1):
    a = int(input())
    # bより大きい最小要素のindex/value
    ind = bisect_right(q, a*(-1))
    ind = ind if 0 <= ind < len(q) else None
    if ind is None:
        q.append(a*(-1))
    else:
        q[ind] = a*(-1)

print(len(q))

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

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

D = deque([])

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

print(len(D))

Submission status: Accepted

Solution code:
import bisect

n = int(input())
seq = []
for i in range(n):
    seq.append(int(input()))
seq.reverse()
LIS = [seq[0]]
for i in range(1,len(seq)):
    if seq[i] >= LIS[-1]:
        LIS.append(seq[i])
    else:
        LIS[bisect.bisect_right(LIS, seq[i])] = seq[i]

print(len(LIS))

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)
B = [A[0]]
for i in range(1, N):

    if A[i] > B[-1]:#2分探索でどこかに入れる
        sm = -1
        la = len(B)-1
        
        while sm+1<la:
            mi = (sm+la)//2
            if B[mi]<A[i]:
                la=mi
            else:
                sm=mi
        B[la]=A[i]
        
    else:#Bに追加
        B.append(A[i])

print(len(B))

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
dp = [10**10]*(n)
for i in range(n):
    r = br(dp, -a[i])
    dp[r] = -a[i]
print(n - dp.count(10**10))

Submission status: Accepted

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

S = [A[0]]
for i in range(1, N):
    if A[i] <= S[0]:
        S.insert(0, A[i])
        continue
    ok = 0
    ng = len(S)
    tmp = (ok+ng)
    while ok+1 < ng:
        tmp = (ok+ng)//2
        if A[i] > S[tmp]:
            ok = tmp
        else:
            ng = tmp
    S[ok] = A[i]
print(len(S))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
from bisect import bisect_left

def main():
    N, *A = map(int, open(0))
    # 方針: 色ごとに最大値をリストで保持する
    # 新しく色を追加しないといけない時は持っている全ての数字より小さい時->先頭追加なのでdequeがいい
    # dequeをbisectで二分探索できるんだ...
    q = deque([])
    for i in range(N):
        d = bisect_left(q,A[i])
        if d == 0:
            q.appendleft(A[i])
        else:
            q[d-1] = A[i]
    print(len(q))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def binary_search(lis,i):
    ng = 0
    ok = len(lis)-1
    while abs(ok-ng) > 1:
        #print(ok,ng)
        mid = (ok + ng) // 2
        if lis[mid] > i:
            ok = mid
        else:
            ng = mid
    return ok

#print(A)
d = [-1,1000000007]
for i in range(N):
    p = binary_search(d,A[i])
    if p == len(d)-1:
        d.append(A[i])
        d[-1],d[-2] = d[-2],d[-1]
    else:
        d[p] = A[i]
    #print(p)
    #print(d)
print(len(d)-2)

Submission status: Accepted

Solution code:
from bisect import bisect
import heapq

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

for i in range(N):
  ii = bisect(q,A[i])
  if ii == len(q):
    heapq.heappush(q,A[i])
  else:
    q[ii] = A[i]
    
print(len(q))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [INT() for _ in range(N)]

seq = A[::-1]
LIS = [seq[0]]
for i in range(1, N):
	if LIS[-1] <= seq[i]:
		LIS.append(seq[i])
	else:
		LIS[bisect(LIS, seq[i])] = seq[i]

print(len(LIS))

Submission status: Accepted

Solution code:
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    A=[0]*n
    for i in range(1,n+1):
        A[-i]=int(input())
    inf=10**10    
    dp=[inf]*(n+1)
    dp[0]=0
    for AA in A:
        bis=bisect.bisect_right(dp, AA)
        dp[bis]=AA #n以下の個数を数える
    print(bisect.bisect_right(dp, inf-100)-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys

N = int(input())
now = int(sys.stdin.readline().strip())
ans = [now]

for n in range(N - 1):
    now = int(sys.stdin.readline().strip())

    if now > ans[0]:
        ans[0] = now
    elif ans[-1] >= now:
        ans.append(now)
    else:
        # 2部探査で行進位置を探る
        left = 0  # 挿入不可能
        right = len(ans) - 1  # 挿入可能

        while right - left > 1:
            mid = (right + left) // 2
            if now > ans[mid]:
                right = mid
            else:
                left = mid

        ans[right] = now

print(len(ans))

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys
import bisect

N = int(input())
now = int(sys.stdin.readline().strip())
ans = [now]

for n in range(N - 1):
    now = int(sys.stdin.readline().strip())

    if now > ans[0]:
        ans[0] = now
    elif ans[-1] >= now:
        ans.append(now)
    else:
        # 2部探査で行進位置を探る
        left = 0  # 挿入不可能
        right = len(ans) - 1  # 挿入可能

        while right - left > 1:
            mid = (right + left) // 2
            if now > ans[mid]:
                right = mid
            else:
                left = mid

        ans[right] = now

print(len(ans))

    # if ans:  # 最初の入力以外であり、すでに追加対象のリストが存在する
    #     if ans[0][-1] < now:
    #         ans[0].append(now)
    #     elif ans[-1][-1] >= now:
    #         appending = [now]
    #         ans.append(appending)
    #     else:
    #         # 二分探索で追加するリストの位置を特定する
    #         left = 0   # 追加できない  ans[left][-1] > now
    #         right = len(ans) - 1  # ans[right][-1] < now
    #
    #         while right - left > 1:
    #             mid = (right - left) // 2
    #             if ans[mid][-1] < now:
    #                 right = mid
    #             else:
    #                 left = mid
    #         ans[right].append(now)
    # else:
    #     appending = [now]
    #     ans.append(appending)

    # for a in ans:
    #     if a[-1] < now:
    #         a.append(now)
    #         break
    # else:
    #     appending = [now]
    #     ans.append(appending)

# print(len(ans))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [INT() for _ in range(N)]

color_max = deque([])
cnt = 0

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

print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
import bisect

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

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

print(len(Q))

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
A,c = list(range(N)),[]
for i in range(N):
	A[i] = int(input())

for x in reversed(A):
	p = bisect_left(c, x+1)
	if p == len(c):
		c.append(x)
	else:
		c[p] = x
print(len(c))

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

for x in A:
	p = bisect_left(c, x+1)
	if p == len(c):
		c.append(x)
	else:
		c[p] = x
print(len(c))

Submission status: Accepted

Solution code:
import heapq
import bisect
N=int(input())
A=[]

for i in range(N):
  a=int(input())
  A.append(a)
h=[]
c=0
for i in range(N-1,-1,-1):
  p=bisect.bisect_right(h,A[i])
  if p==len(h):
    h.append(A[i])
    c+=1
  else:
    h[p]=A[i]
print(c)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
N = int(input())
seq = [0] * N
for i in range(N):
  seq[i] = (-1) * int(input())

"""
#リストseqからLISの長さを出す
LIS = [seq[0]]
for i in range(len(seq)):
    if seq[i] >= LIS[-1]:
        LIS.append(seq[i])
    else:
        LIS[bisect_right(LIS, seq[i])] = seq[i]

print(len(LIS) - 1)
#print(LIS)
"""
def getLIS(_N,a):
  INF = 1e18
  MaxP = _N+10
  dp = [INF for _ in range(MaxP)]
  for i in range(_N):
    dp[bisect_right(dp,a[i])] = a[i]

  #print(dp[:10])
  return dp[:bisect_left(dp, INF)]

LIS2 = getLIS(N,seq)

print(len(LIS2))

Submission status: Accepted

Solution code:
from bisect import bisect

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

ans = [1] * n
for ai in ma:
    tmp = bisect(ans, ai)
    ans[tmp] = ai
print(sum(num <= 0 for num in ans))

Submission status: Accepted

Solution code:
from bisect import bisect

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

ans = [ma[0]]
for ai in ma[1:]:
    tmp = bisect(ans, ai)
    if tmp == len(ans):
        ans.append(ai)
    elif tmp < len(ans):
        ans[tmp] = ai
print(len(ans))