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, copy, heapq, math
from math import inf
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

now=n
lst=[-1]*n

for i in range(n):
    tmp=bisect.bisect_left(lst,a[i])
    if tmp==now:
        lst[tmp-1]=a[i]
        now-=1
    else:
        lst[tmp-1]=a[i]
# print(lst)
print(n-now)

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 + 1)
for i in a:
    dp[bisect_left(dp, i) - 1] = i
print(dp[::-1].index(-float("inf")))

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=[I() for i in range(n)]
cols=deque([inf])
i=0
while i<n:
    #print(cols)
    x=lis[i]
    if cols[0]>=x:
        cols.appendleft(x)
    else:
        cols[bisect_left(cols,x)-1]=x
        #print(bisect_left(cols,x))
    i+=1
#print(cols)
print(len(cols)-1)

Submission status: Accepted

Solution code:
def LIS(A):
    dp = [-A[0]]
    for a in A[1:]:
        if -a >= dp[-1]:
            dp.append(-a)
        else:
            dp[bisect_right(dp, -a)] = -a
    return len(dp)

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

import sys
input = sys.stdin.readline
from bisect import bisect_right

N = int(input())
A = list(map(int, sys.stdin.readlines()))

print(LIS(A))

Submission status: Accepted

Solution code:
def LIS(A):
    dp = [-next(A)]
    for a in A:
        if -a >= dp[-1]:
            dp.append(-a)
        else:
            dp[bisect_right(dp, -a)] = -a
    return len(dp)

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

import sys
input = sys.stdin.readline
from bisect import bisect_right

A = (int(input()) for _ in range(int(input())))

print(LIS(A))

Submission status: Accepted

Solution code:
def LIS(A):
    dp = [-A[0]]
    for a in A[1:]:
        if -a >= dp[-1]:
            dp.append(-a)
        else:
            dp[bisect_right(dp, -a)] = -a
    return len(dp)

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

import sys
input = sys.stdin.readline
from bisect import *

N = int(input())

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

print(LIS(A))

Submission status: Accepted

Solution code:
def LIS(A):
    dp = deque([A[0]])
    for a in A[1:]:
        if a <= dp[0]:
            dp.appendleft(a)
        else:
            dp[bisect_left(dp, a)-1] = a
    return len(dp)

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

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

N = int(input())

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

print(LIS(A))

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 num>=DP[-1]:
        DP.append(num)
    else:
        index=bisect_right(DP,num)
        DP[index]=num
print(len(DP))

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 num>=DP[-1]:
        DP.append(num)
    else:
        index=bisect_right(DP,num)
        DP[index]=num
print(len(DP))

Submission status: Accepted

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

N = int(readline())
ans = []
import bisect
for i in range(N):
  a = -int(readline())
  ind = bisect.bisect_right(ans, a)
  if ind == len(ans):
    ans.append(a)
  else:
    ans[ind] = a
    
print(len(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:

from bisect import bisect_right

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

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
for i in range(N):
    dp[bisect_right(dp, -X[i])] = -X[i]

print(sum(v < INF for v in dp))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
colors = [-1]*(n+1)
for _ in range(n):
    a = int(input())
    idx = bisect.bisect_left(colors, a)-1
    colors[idx] = a
print(n-bisect.bisect_left(colors, 0)+1)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
colors = [-1]*(n+1)
for _ in range(n):
    a = int(input())
    idx = bisect.bisect_left(colors, a)-1
    colors[idx] = a
print(colors[::-1].index(-1))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

def LIS(arr):  #bisect.bisect_left
    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 = []
for i in range(N):
    A.append((-int(input()), i))

print(LIS(A))

Submission status: Accepted

Solution code:
from bisect import bisect_right
def LIS(l):
    length = [l[0]]
    for i in range(1, len(l)):
        if l[i] >= length[-1]:
            length.append(l[i])
        else:
            pos = bisect_right(length, l[i])
            length[pos] = l[i]
    return len(length)

n = int(input())
a = [int(input()) for i in range(n)]
a = a[::-1]
print(LIS(a))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right, bisect_left
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(int(readline()) for _ in range(N))

    LIS = [INF]*N
    A.reverse()
    for a in A:
        i = bisect_right(LIS,a)
        LIS[i] = a
    print(bisect_left(LIS, INF))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#「与えられた数列の、広義単調減少列の長さの最大値 L」
from bisect import bisect_left, bisect_right
n = int(input())
INF = 1010101010
dp = [INF] * n
a = [int(input()) for _ in range(n)]
a.reverse()
for i in a:
    dp[bisect_right(dp, i)] = i
print(bisect_left(dp, INF))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
n = int(input())
INF = 1010101010
dp = [INF] * n
a = [int(input()) for _ in range(n)]
a.reverse()
for i in a:
    dp[bisect_right(dp, i)] = i
print(bisect_left(dp, INF))

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left

N = int(input())
A = []
for _ in range(N):
    x = int(input())
    idx = bisect_left(A, x)
    if idx == 0:
        A.insert(idx, x)
    elif A[idx-1] == x:
        A.insert(idx, x)
    else:
        A[idx-1] = x
#    print(A,x)
print(len(A))

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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

buf = deque()
for a in A:
    i = bisect.bisect_right(buf, a-1)-1
    if i < 0:
        buf.appendleft(a)
    else:
        buf[i] = a
print(len(buf))

Submission status: Accepted

Solution code:
from bisect import bisect_right
N = int(input())
A = [int(input()) for i in range(N)]
A.reverse()
X = [A[0]]

for i in range(1, N):
    if X[-1] <= A[i]:
        X.append(A[i])
    else:
        idx = bisect_right(X, A[i])
        X[idx] = A[i]

print(len(X))

Submission status: Accepted

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

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

print(len(X))

Submission status: Accepted

Solution code:
from bisect import bisect

n=int(input())
a=[0]*n
for i in range(n):
    a[i]=-int(input())

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -10**10
    
    for i in range(n):
        idx = bisect(dp, a[i])
        dp[idx] = min(a[i], dp[idx])

    return dp

dp=loopa()        

print(bisect(dp, 10**10-1)-1)

Submission status: Accepted

Solution code:
from bisect import bisect

icase=1
if icase==1:
    n=int(input())
    a=[0]*n
    for i in range(n):
        a[i]=-int(input())
elif icase==2:
    n=5
    a=[-2,-1,-4,-5,-3]
elif icase==3:
    n=4
    a=[0,0,0,0]

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -10**10
    
    for i in range(n):
#        idx = bisect(dp, a[i]-1)
        idx = bisect(dp, a[i])
        dp[idx] = min(a[i], dp[idx])

#        print("i:",i,"a:",a,"dp2:",dp2)            
    return dp

dp=loopa()        

print(bisect(dp, 10**10-1)-1)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

N=int(input())
minList=deque([])
minmax=-1
for i in range(N):
  if i==0:
    a=int(input())
    minList.append(a)
    minmax=a
  else:
    a=int(input())
    if a<=minmax:
      minmax=a
      minList.appendleft(a)
    else:
      idx=bisect_left(minList,a)
      if idx==1:minmax=a
      minList[idx-1]=a
print(len(minList))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    A = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    if N==1:
        print(1)
        return

    l=[-A[0]]
    for a in A[1:]:
        ind=bisect_right(l,-a)
        if ind==len(l):
            l.append(-a)
        else:
            l[ind]=-a
    print(len(l))






if __name__ == "__main__":
    main()

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(int(input()) for _ in range(n))

    que = deque([A[0]])
    for i in range(1, n):
        idx = bisect_left(que, A[i])
        if idx == 0:
            que.appendleft(A[i])
        else:
            idx -= 1
            que[idx] = A[i]
    print(len(que))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
###==================================================
### import
import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N = iIn()
A = iInLV(N)

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

print(len(lst))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N = I()
A = ILs(N)

MAXS = [1 for i in range(N)]
for a in A:
  p = bisect.bisect_right(MAXS,-a)
  MAXS[p] = -a
ans = 0
for i in MAXS:
  if i != 1:
    ans += 1
  else:
    break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_right
N = int(input())
A = [int(input()) for _ in range(N)]
ans = 1
min_vs = [A[-1]]
for i in range(N-2, -1, -1):
    a = A[i]
    idx = bisect_right(min_vs, a)
    if idx == len(min_vs):
        ans += 1
        min_vs.append(a)
    else:
        min_vs[idx] = a
print(ans)

Submission status: Accepted

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

dp = deque([])
l = len(A)
for i,a in enumerate(A):
  pos = bisect.bisect_left(dp, a)-1
  if pos<0:
    dp.appendleft(a)
  else:
    dp[pos] = a

print(len(dp))

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())

N = I()
A = [-I() for i in range(N)]

# Aの最大非増加部分列の長さを求めればOK

from bisect import bisect_left,bisect

def LNDS(l):  #リストlのLNDSの長さを求める
    dp = [float('inf')]*(len(l)+1)
    dp[0] = -float('inf')
    for i in range(len(l)):
        j = bisect(dp,l[i])
        dp[j] = l[i]
    return bisect_left(dp,float('inf'))-1

print(LNDS(A))

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())

N = I()
A = [-I() for i in range(N)]

# Aの最大非増加部分列の長さを求めればOK

from bisect import bisect,bisect_left

def LIS(l):  #リストlのLISの長さを求める
    dp = [float('inf')]*(len(l)+1)
    dp[0] = -float('inf')
    for i in range(len(l)):
        j = bisect(dp,l[i])
        dp[j] = l[i]
    return bisect_left(dp,float('inf'))-1

print(LIS(A))

Submission status: Accepted

Solution code:
# Longest non-increasing subsequenceの長さを求める
import sys
input = sys.stdin.readline

def bisect_right_reverse(L, target):
    ok = len(L)
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if L[mid] < target:
            ok = mid
        else:
            ng = mid
    return ok

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

dp = [-1]  # A[i] >= 0なので、A[0] > dp[0]となる。
for i in range(N):
    k = bisect_right_reverse(dp, A[i])
    if k == len(dp):
        dp.append(A[i])
    else:
        dp[k] = A[i]

print(len(dp))

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

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

queue = deque()

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

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

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

import collections, bisect
queue = collections.deque()

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

Submission status: Accepted

Solution code:
# YouTube解説の方法（deque使わない）
import sys
input = sys.stdin.readline

def bisect_right_reverse(L, target):
    ok = len(L)
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if L[mid] < target:
            ok = mid
        else:
            ng = mid
    return ok

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

L = []
for i in range(N):
    k = bisect_right_reverse(L, A[i])
    if k == len(L):
        L.append(A[i])
    else:
        L[k] = A[i]

print(len(L))

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(int(input()) for _ in range(n))

    LIS = deque()
    for i in range(n):
        if len(LIS) == 0:
            LIS.appendleft(A[i])
        else:
            idx = bisect_left(LIS, A[i])
            if idx == 0:
                LIS.appendleft(A[i])
            else:
                LIS[idx - 1] = A[i]
    print(len(LIS))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
import bisect

N = int(input())
h = deque([int(input())])

for _ in range(N-1):
  a = int(input())
  i = bisect.bisect_left(h, a)
  if i == 0:
    h.appendleft(a)
  else:
    h[i-1] = a
    
print(len(h))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

input = sys.stdin.readline


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

    A = [-a for a in A]

    colors = []
    for a in A:
        idx = bisect_right(colors, a)
        if idx == len(colors):
            colors.append(a)
        else:
            colors[idx] = a

    ans = len(colors)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

input = sys.stdin.readline


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

    colors = []
    for a in A:
        idx = bisect_left(colors, a)
        if idx == 0:
            colors.insert(0, a)
        else:
            colors[idx - 1] = a

    ans = len(colors)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, insort_right

input = sys.stdin.readline


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

    colors = []
    for a in A:
        idx = bisect_left(colors, a)
        if idx != 0:
            colors.pop(idx - 1)
        insort_right(colors, a)

    ans = len(colors)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline #inputに置き換え可能

from bisect import bisect

# N: 数列の長さ
# A[i]: a_i の値
def solve(N, A):
    INF = 10**10

    dp = [INF]*(N+1)
    dp[0] = -1
    for a in A:
        idx = bisect(dp, a)
        dp[idx] = min(a, dp[idx])
    return max(i for i in range(N+1) if dp[i] < INF)

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

print(solve(n, a))

Submission status: Accepted

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

print(len(que))

Submission status: Accepted

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

# map(int, input().split())

MOD = 10 ** 4 + 7

N = int(input())

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

from collections import deque
d = deque([])
for a in A:
    l = -1
    r = len(d)
    while r - l > 1:
        m = l + (r - l) // 2
        if d[m] >= a:
            r = m
        else:
            l = m
    if r == 0:
        d.appendleft(a)
    else:
        d[r - 1] = a
print(len(d))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input()) for _ in range(n)]
ans=[-a[0]]
ansl=1
from bisect import bisect_right
for ai in a[1:]:
  tmp=bisect_right(ans,-ai)
  if tmp<ansl:
    ans[tmp]=-ai
  else:
    ans.append(-ai)
    ansl+=1
print(ansl)

Submission status: Accepted

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



if '__main__' == __name__:
    resolve()

Submission status: Accepted

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


S = []
for i in range(N):
    posi = bisect.bisect_left(S,A[i])
    if posi == 0:
        S.insert(0,A[i])
    else:
        S[posi-1] = A[i]

print(len(S))

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

n = int(input())
ans = []
ans.append(int(input()))
ans = deque(ans)
for i in range(n-1):  
  temp = int(input())
  if temp <= ans[0]:
    ans.appendleft(temp)
  else:
    ans[bisect_left(ans, temp)-1]=temp
print(len(ans))

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

n = int(input())
ans = []
ans.append(int(input()))
ans = deque(ans)
for i in range(n-1):  
  temp = int(input())
  #print("ans " +  str(ans) + " temp " + str(temp))
  if temp <= ans[0]:
    #d = deque(ans)
    #d.appendleft(temp)
    #ans = list(d)
    ans.appendleft(temp)
  else:
    ans[bisect_left(ans, temp)-1]=temp
#print(ans)
print(len(ans))

Submission status: Accepted

Solution code:
N=int(input())
L=[1 for i in range(N+1)]
L[0]=-10**10

import bisect
for i in range(N):
    n=int(input())
    L[bisect.bisect_right(L,-n)]=-n
#print(L)
ans=0
for i in range(1,N+1):
    if L[i]==1:
        break
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def bisect_left_reverse(a, x):
    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 bisect_right_reverse(a, x):
    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
  
n = int(input())
data = [int(input())]

for i in range(n-1):
  a = int(input())
  idx = bisect_right_reverse(data, a)
  if idx == len(data):
    data.append(a)
  else:
    data[idx] = a

print(len(data))

Submission status: Accepted

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

n = int(input())
col_maxs = []
for _ in range(n):
    a = int(input()) * (-1)
    if not col_maxs:
        col_maxs.append(a)
        continue

    curr_max = col_maxs[-1]
    if a >= curr_max:
        col_maxs.append(a)
    else:
        # aより大きい最小要素のindex/value
        ind = bisect_right(col_maxs, a)
        col_maxs[ind] = a

print(len(col_maxs))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

n = int(input())
col_maxs = []
for _ in range(n):
    a = int(input()) * (-1)
    if not col_maxs:
        col_maxs.append(a)
        continue

    curr_max = col_maxs[-1]
    if a >= curr_max:
        col_maxs.append(a)
    else:
        # aより大きい最小要素のindex/value
        ind = bisect_right(col_maxs, a)
        col_maxs[ind] = a

print(len(col_maxs))