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:
a=int(input())
b=[int(input()) for i in range(a)]
LIS = [b[0]]
for i in range(1,len(b)):
  if b[i] <= LIS[-1]:
    LIS.append(b[i])
  else:
    lo=0
    hi=len(LIS)
    while lo < hi:
      mid=(lo+hi)//2
      if b[i]>LIS[mid]:
        hi =mid
      else:
        lo=mid+1  
    LIS[lo] = b[i]
print(len(LIS))

Submission status: Accepted

Solution code:
from bisect import bisect
n = int(input())
A = [int(input()) for i in range(n)]
ans = []
for a in A:
    i = bisect(ans,-a)
    if len(ans) == i:
        ans.append(-a)
    else:
        if -a<ans[i]: ans[i]=-a
print(len(ans))

Submission status: Accepted

Solution code:
from bisect import bisect


def main():
    N = int(input())
    A = [-int(input()) for _ in range(N)]
    L = [A[0]]
    for a in A[1:]:
        if a >= L[-1]:
            L.append(a)
        else:
            L[bisect(L, a)] = a
    print(len(L))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
Ans=[A[-1]]
for i in reversed(range(n-1)):
  a=A[i]
  if a>=Ans[-1]:
    Ans.append(a)
  else:

    Ans[bisect.bisect_right(Ans,a)]=a

print(len(Ans))

Submission status: Accepted

Solution code:
import bisect
N=int(input())
X=[-1]*N
for _ in X:a=int(input());X[bisect.bisect_right(X,a-1)-1]=a
print(N-X.count(-1))

Submission status: Accepted

Solution code:
from bisect import bisect_right as f
N=int(input())
X=[-1]*N
for _ in X:a=int(input());X[f(X,a-1)-1]=a
print(N-X.count(-1))

Submission status: Accepted

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

import bisect as bi


def solve():
    N = int(input())
    A = []
    heads = []
    for _ in range(N):
        A.append(int(input()))
    a = A.pop()
    bi.insort(heads, a)
    while A:
        a = A.pop()
        if a < heads[-1]:
            j = bi.bisect(heads, a)
            del heads[j]
        bi.insort(heads, a)
    return len(heads)
  

def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right
N=int(input())
X=[-1]*N
for _ in X:a=int(input());X[bisect_right(X,a-1)-1]=a
print(N-X.count(-1))

Submission status: Accepted

Solution code:
# -*- coding utf-8 -*-
import bisect
from collections import deque

N = int(input())

# c = [int(input())]
c = deque()
c.appendleft(int(input()))


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

print(len(c))

Submission status: Accepted

Solution code:
def bisect_right(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

import collections
n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))
res = collections.deque([])

res.append(dat[0])
import bisect

for i in range(1, n):
    a = bisect_right(res, dat[i])
    #print("2 : {0}".format(a))

    if a == len(res):
        res.append(dat[i])
    else:
        res[a] = dat[i]
print(len(res))
#print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
INF = 10 ** 10
n = int(input())
alst = [int(input()) for _ in range(n)][::-1]
dp = [INF] * (n + 1)
dp[0] = -1
ans = 0
for a in alst:
  ind = br(dp, a)
  dp[ind] = a
  ans = max(ans, ind)
print(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, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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


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

print(len(LIS))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=[int(input()) for i in range(n)]
inf=10**9+1
tmp=[inf]*n
ans=0
for i in range(n-1,-1,-1):
  j= bisect.bisect_right(tmp,a[i])
  tmp[j]=a[i]
for i in range(n):
  if tmp[i]!=inf:
    ans+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import bisect
from collections import deque

fastinput = sys.stdin.readline
N = int(fastinput())
A = [int(fastinput()) for j in range(N)]
surface = deque([A[0]])#常に小さい順にソートされている
surfMax = A[0]
surfMin = A[0]
color = 1
for n,a in enumerate(A):
    if n==0:continue

    if color == 1:
        c = surface[0]
        if a>c:
            surface[0] = a
            surfMax = a
            surfMin = a
        if a==c:
            surface.appendleft(a)
            color += 1
        if a<c:
            surface.appendleft(a)
            color += 1
            surfMin = a

    else:    
        if a<=surfMin:
            color += 1
            surface.appendleft(a)
            surfMin = a
        elif a>surfMax:
            surface[color-1] = a
            surfMax = a
        else:
            pos = bisect.bisect_left(surface,a) -1 #a未満の最大の整数
            surface[pos] = a
            if pos==0:
                surfMin = a
            if pos == color-1:
                surfMax = a
print(color)

Submission status: Accepted

Solution code:
"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return self.data[self.size:]

from operator import eq

N = int(input())

B = sorted((v,-i) for i,v in enumerate(int(input()) for _ in range(N)))
B = [-i for v,i in B]
i_j = {j:i for i,j in enumerate(B)}

st = SegmentTree.from_initial_data(min, equality=eq, identity=N, data=B)

visit_cnt = 0
cnt = 0
while visit_cnt < N:
    j = 0
    while True:
        i = st[j:]
        if i == N:
            break
        j = i_j[i]
        visit_cnt += 1
        st[j] = N
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
def seek(value):
    right = len(color_list) - 1
    left = 0
    while(True):
        mid = (right + left) // 2
        if(value > color_list[mid]):
            right = mid
        else:
            left = mid
        if(right - left <= 1):
            return right

N = int(input())    
color_list =  [int(input())]
for i in range(N-1):
    new_value = int(input())
    if(new_value > color_list[0]):
        color_list[0] = new_value
    elif(new_value <= color_list[-1]):
        color_list.append(new_value)
    else:
        new_index = seek(new_value)
        color_list[new_index] = new_value
print(len(color_list))

Submission status: Accepted

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

N=int(input())
A=[-int(input()) for _ in range(N)]
l=[A[0]]
for x in A[1::]:
    tmp=bisect.bisect(l,x)
    if tmp==len(l):l.append(x)
    else: l[tmp]=x
print(len(l))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

b = []
for i in range(n):
    k = bisect.bisect(b,-a[i])
    if k == len(b):
        b.append(-a[i])
    else:
        b[k] = -a[i]

print(len(b))

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

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

print(len(L))

Submission status: Accepted

Solution code:
from bisect import bisect as bisect
def LIS(l):
    seq = []
    for a in l:
        i = bisect(seq,a)
        if len(seq)==i:
            seq.append(a)
        else:
            seq[i]=a
    return len(seq)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import bisect

# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 

# color
c = [-999]*n

for i in range(0,n):
#    if c[0] >= a[i]:
#        c.insert(0,a[i])
#    else:
    p = bisect.bisect_left(c, a[i])
    c[p-1]=a[i]
#        print(c)
#        print(p)

print(len(c) - bisect.bisect_left(c, -1))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
import sys
#import bisect
sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]

def bisect(ls,x):
    l,r=0,len(ls)
    while r-l>1:
        mid=(l+r)//2
        if ls[mid]>=x: # condition
            r=mid
        else:
            l=mid
    #print('bisect',ls,x,'=',r)
    return l

n=I()
a=deque()
q=[[] for _ in range(n)]
m=0 # num of queue now
for i in range(n):
    a+=[I()]
#print('a=',a)

q=deque()
q.append(a.popleft())
#print(q,'q[',0,']=')

while a:
    c=a.popleft()
    if c<=q[0]:
        q.appendleft(c)
        #print(q,'q[',0,']=',c)
    else:
        i=bisect(q,c)
        q[i]=c
        #print(q,'q[',i,']=',c)


ans=len(q)
print(ans)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
Ans=[A[-1]]
for i in reversed(range(n-1)):
  a=A[i]
  if a>=Ans[-1]:
    Ans.append(a)
  else:

    Ans[bisect.bisect_right(Ans,a)]=a

print(len(Ans))

Submission status: Accepted

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

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

print(sum(dp[i] < INF for i in range(N)))

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):

    A.reverse()
    res = [A[0]]
    for i in A[1:]:
        pos = bisect(res,i)
        if len(res) <= pos:
            res.append(i)
        else:      
            res[pos] = i

    print(len(res))
    return


# Generated by 1.1.4 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():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
 
 
def main():
    n = input()
    aa = []
    xx = [-input()]
    for _ in xrange(n - 1):
        aa.append(-input())
    for a in aa:
        if a >= xx[-1]:
            xx.append(a)
        else:
            i = bisect.bisect_right(xx, a)
            if i == len(xx):
                i -= 1
            xx[i] = a
    print len(xx)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

color = 1
A[0] = int(input())


def search(A, color, a):
        left = 0
        right = color - 1
        signal = 0
        while left < right:
                mid = (left + right) // 2
                if A[mid] == a - 1:
                        return mid
                        signal = 1
                elif a <= A[mid]:
                        left = mid + 1
                else:
                        right = mid
        if signal == 0:
                return left


for i in range(N - 1):
        
        a = int(input())
        num = search(A, color, a)
        if num == color - 1 and a <= A[num]:
                A[color] = a
                color += 1
        else:
                A[num] = a

print(color)

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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

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

print(len(ans))

Submission status: Accepted

Solution code:
import bisect

if __name__ == '__main__':
    n = int(input())
    a = [int(input()) for _ in range(n)]
    colors = [a[-1]]
    ans = 1
    for x in reversed(a[:-1]):
        i = bisect.bisect_left(colors, x + 1)
        if i == ans:
            ans += 1
            colors.append(x)
        else:
            colors[i] = x
    print(ans)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N = _I()
A = [_I() for i in range(N)]

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

def bisect(arr, val, cmp):
    l = -1
    r = len(arr)
    while r - l > 1:
        e = (l + r) >> 1
        if cmp(arr[e], val): l = e
        else: r = e
    return r

res = [] 
for a in A:
    #  print('a res', a, res)
    if len(res) == 0:
        res.append(a)
    else:
        if a <= res[-1]:
            # 小さいので追加
            res.append(a)
        else:
            # 入れ替え
            p = bisect(res, a, lambda x, y: x > y)
            if res[p] == a:
                p = bisect(res, a-1, lambda x, y: x > y)
                res[p] = a
            else:
                res[p] = a

print(len(res))

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = []

a = int(input())

val = [-a]
length = 1

for _ in range(N - 1) :
    a = int(input())
    a *= -1
    i = 0

    index = bisect.bisect_right(val, a)
    if index >= length :
        val.append(a)
        length += 1
    else :
        val[index] = a

print(length)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 20 20:53:54 2019

@author: ctiuser
"""

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

ans = [A[0]]

for i in range(1,N):
    l,r = 0, len(ans)-1
    p = (r-l)//2 + 1
    if A[i] <= ans[r]:
        ans.append(A[i])
    elif A[i] > ans[l]:
        ans[l] = A[i]
    else:
        tmp = r
        while r - l > 1:
            if A[i] > ans[p]:
                tmp = p
                r = p
                p = (r-l)//2 + l
            else:
                l = p
                p = (r-l)//2 + l
        ans[tmp] = A[i]
#    print(i,ans)
print(len(ans))

Submission status: Accepted

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
    def ope(self, x, y):
        return x + y
    def update(self, i, v):
        while i <= self.n:
            self.data[i] = self.ope(self.data[i], v)
            i += i & -i
    def query(self, i):
        ret = 0
        while 0 < i:
            ret = self.ope(self.data[i], ret)
            i &= i - 1
        return ret
    def lower(self, w):
        if w <= 0:
            return 0
        x = 0
        k = 2**(self.n.bit_length())
        while k:
            if x + k <= self.n and  self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k >>= 1
        return x + 1



n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(list(set(a)))
d = {}
for i, j in enumerate(b):
    d[j] = i
a = [d[i] for i in a]
k = len(d)

B = BIT(k)
ans = 0
for i in a:
    i = i+1
    q = B.query(i)
    if q == 0:
        B.update(i, 1)
        ans += 1
    else:
        v = B.lower(q)
        if v != i:
            B.update(v, -1)
            B.update(i, 1)
        else:
            w = B.query(i-1)
            if w == 0:
                B.update(i, 1)
                ans += 1
            else:
                v = B.lower(w)
                B.update(v, -1)
                B.update(i, 1)
print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import deque

N = int(input())

# c = [int(input())]
c = deque()
c.appendleft(int(input()))


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

print(len(c))

Submission status: Accepted

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

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

l = deque([])

for i in range(N):
    if l == []:
        l.append(A[i])
    else:
        index = bisect.bisect_right(l, A[i])
        index2 = bisect.bisect_left(l, A[i])
        if index == 0:
            l.appendleft(A[i])
        elif index != index2:
            if index2 == 0:
                l.appendleft(A[i])
            else:
                l[index2-1] = A[i]
        else:
            l[index-1] = A[i]

print(len(l))

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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

B = []
min = -10000000000
for i in range(N):
	loc = bisect.bisect_right(B, -A[i])
	if loc == len(B):
		B.append(-A[i])
	else:
		B[loc] = -A[i]

print(len(B))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import bisect

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

x = [A[0]]

for a in A[1:]:
    i = bisect.bisect(x,a)
    if i==len(x): x.append(a)
    else: x[i]=a

print(len(x))

Submission status: Accepted

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

tree = deque([[A[0]]])
leaf = deque([A[0]])
for n in range(1,N):
    a = A[n]
    pos = min(n-1,bisect.bisect_left(leaf,a)-1)
    if pos==-1:
        tree.appendleft([a])
        leaf.appendleft(a)
    else:
        tree[pos].append(a)
        leaf[pos] = a
print(len(tree))

Submission status: Accepted

Solution code:

def binSearch(S, x):
    a = -1
    b = len(S)-1

    while(a + 1 < b):
        c = (a+b)//2
        if S[c] >= x:
            a = c
        else:
            b = c

    return b

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

    S = []

    for a in A:
        if len(S) == 0 or S[-1] >= a:
            S.append(a)
        else:
            p = binSearch(S, a)
            S[p] = a
    
    print(len(S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import *
from bisect import bisect_right, bisect_left
from collections import deque
N = int(input())
A = [int(input()) for i in range(N)]
lb, ub = 0, N
while lb + 1 < ub:
    mid = (lb+ub)//2
    cnt, ms, flag = 1, deque(), 1
    ms.append(A[0])
    for a in A[1:]:
        if a <= ms[0]:
            ms.appendleft(a)
            cnt += 1
            if cnt > mid:
                flag = 0
                break
        else:
            i = bisect_left(ms, a)-1
            ms[i] = a
    if flag:
        ub = mid
    else:
        lb = mid
cnt, ms, flag = 1, deque(), 1
ms.append(A[0])
for a in A[1:]:
    if a <= ms[0]:
        ms.appendleft(a)
        cnt += 1
        if cnt > mid:
            flag = 0
            break
    else:
        i = bisect_left(ms, a)-1
        ms[i] = a
if flag:
    print(mid)
else:
    print(mid+1)

Submission status: Accepted

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

N = int(input())
L = [-1 * int(input())]
for _ in range(N - 1):
    a = -1 * int(input())
    if a >= L[-1]:
        L.append(a)
        continue

    i = bisect.bisect_right(L, a)
    L[i] = a

print(len(L))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in [0]*N]
B = [A[0]]
ans = 1

for a in A[1:]:
    l = 0
    r = ans - 1
    if B[0]<a:r=0
    while l+1<r:
        i = (l+r)//2
        if B[i] < a:
            r = i
        else:
            l = i
    if B[r]<a:B[r] = a
    else:
        B.append(a)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

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

list_ = deque([As[0]])
for a in As[1:]:
    i = bisect_left(list_, a) - 1
    if i < 0:
        list_.appendleft(a)
    else:
        list_[i] = a
print(len(list_))

Submission status: Accepted

Solution code:
import sys, math
from collections import deque

readline = sys.stdin.readline

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


heads = []

for a in A:
    if len(heads) == 0:
        heads.append(a)
    else:
        left = 0
        right = len(heads) - 1
        while right - 1 > left:
            mid = (left + right) // 2
            if a <= heads[mid]:
                left = mid + 1
            else:
                right = mid

        if a > heads[left]:
            heads[left] = a
        elif a > heads[right]:
            heads[right] = a
        else:
            heads.append(a)

print(len(heads))

Submission status: Accepted

Solution code:
import bisect

n=int(input())
a1=int(input())
alist=[]
for al in range(n-1):
    alist.append(-2)
alist.append(a1)

for i in range(n-1):
    an=int(input())
    #print(alist,an)
    index = bisect.bisect_left(alist, an)
    alist[index-1]=an

#print(alist)
index = bisect.bisect_left(alist, -1)
#print(index)
print(len(alist)- index)

Submission status: Accepted

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

from bisect import bisect

h = []

for ai in a:

    ix = bisect(h, -ai)
    if ix == len(h):
        h.append(-ai)
    else:
        h[ix] = -ai

print(len(h))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def main():
    N = II()
    a_list = []

    for i in range(N):
        a = II()
        a_list.append(a)


    from bisect import bisect_left
    from collections import deque
    g = deque()

    for i in range(N):
        a = a_list[i]
        if len(g) == 0:
            g.appendleft(a)
        else:
            pos = bisect_left(g, a)
            dprint(g, a, pos)
            if pos >= 1:
                g[pos-1] = a
            else:
                #g.insert(0, a)
                g.appendleft(a)
    dprint(g)
    print(len(g))
main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right, insort

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

def main():
  n = I()
  a = [I() for i in range(n)]
  b = []

  for i in range(n-1, -1, -1):
    t = bisect_right(b, a[i])
    if len(b)-1<t or b[t]==a[i]:
      insort(b, a[i])
    else:
      b[t] = a[i]
  print(len(b))

if __name__ == '__main__':
  main()

Submission status: Accepted

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

from bisect import bisect_right
	
def LIS(L) :   
    lis = [L[0]]
    for a in L[1:] :
        if a >= lis[-1] :
            lis.append(a)
        else :
            s = bisect_right(lis, a)
            lis[s] = a
    return len(lis)

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

Submission status: Accepted

Solution code:
def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

n = int(input())
f = int(input())
ans = [-f]
for i in range(n-1):
    now = -int(input())
    j = bisect_right(ans,now)
    if j == len(ans):
        ans.append(now)
    else:
        ans[j] = now

print(len(ans))

Submission status: Accepted

Solution code:
from bisect import bisect_left


def li():
    return list(map(int, input().split()))


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

    color_list = [-1] * n
    color_num = 0

    for a in a_list:
        # ２分探索
        index = bisect_left(color_list, a)
        # print(index)
        color_list[index - 1] = a
        if n - index == color_num:
            color_num = color_num + 1
        # print(color_list)
    # print()
    # print(color_list)
    print(color_num)

# a1から順番に塗っていく
# 色ごとに、今まで塗った最大値を記録する
# 既存の色でぬれる場合は、なるべく最大値の増分が少なくなるように色を選ぶ
# 既存の色でぬれない場合は新しい色を作って最大値を記録する

Submission status: Accepted

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

B = [A[0]]

for i in range(1,N):
    if A[i]<=B[-1]:
        B.append(A[i])
    elif A[i]>B[0]: 
        B[0] = A[i]
    else:
        l = 0
        r = len(B)-1
        while l+1<r:
            c = (l+r)//2
            if B[c]>=A[i]:
                l = c
            else:          
                r = c
        if B[l]<A[i]:
            B[l] = A[i]
        else:
            B[r] = A[i]
print(len(B))

Submission status: Accepted

Solution code:
import bisect
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = []
for i in range(n):
    a.append(ni())
a = a[::-1]
hs = [999999999999] * (n+1)
lis = 0
for v in a:
    pos = bisect.bisect_right(hs, v)
    hs[pos] = v
    lis = max(lis, pos+1)
print(lis)

Submission status: Accepted

Solution code:
import bisect
from collections import deque


n = int(input())
lines = deque()
for _ in range(n):
    a = int(input())

    index = bisect.bisect_left(lines, a)
    if index == 0:
        lines.appendleft(a)
        continue
    
    lines[index - 1] = a

print(len(lines))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right, insort_left
from collections import deque
N = int(sys.stdin.readline())
a_list = [int(sys.stdin.readline()) for _ in range(N)]


que = []
que = deque(que)

ans = 0
min_num = float("inf")
for i, a in enumerate(a_list):
    if i == 0:
        que.append(a)
        min_num = a
        ans += 1
    else:
        idx = bisect_right(que, a-1)

        if idx == 0:
            que.appendleft(a)
            ans += 1
            min_num = a
        else:
            idx = bisect_right(que, a-1)
            que[idx-1] = a
            if idx -1 == 0:
                min_num = a
    #print(que, min_num)
print(ans)