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

input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    n = [A.pop(-1)]
    A.reverse()
    
    for a in A:
        if n[-1] <= a: n.append(a)
        else: n[bisect_right(n, a)] = a
    
    print(len(n))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_right

def main():    
    N = int(input())
    A = [int(input()) for i in range(N)]
    n = [A.pop(-1)]
    A.reverse()
    
    for a in A:
        if n[-1] <= a: n.append(a)
        else: n[bisect_right(n, a)] = a
    
    print(len(n))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=[int(input()) for i in range(n)]
l=[-1]*n
ans=0
for i in range(n):
  l[bisect.bisect_left(l,a[i])-1]=a[i]
print(n-l.count(-1))

Submission status: Accepted

Solution code:
from bisect import bisect_right
N = int(input())
A = []
for i in range(N):
    A.append(-int(input()))
INF = float('inf')
D = [INF] * N
for i in range(len(A)):
  
    D[bisect_right(D, A[i])] = A[i]

print(N - D.count(INF))

Submission status: Accepted

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

a=[-int(input()) for _ in range(n)]
x=[a[0]]
for i in a[1:]:
  y=bisect.bisect(x,i)
  if y==len(x):x.append(i)
  else:x[y]=i
print(len(x))

Submission status: Accepted

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

Submission status: Accepted

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

from collections import deque

import bisect
n = int(input())

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

#color = [a[0]]

d = deque()
d.appendleft(a[0])

for i in range(1,n):
    idx = bisect.bisect_left(d,a[i])
    if idx == 0:
        d.appendleft(a[i])
    else:
        d[idx-1] = a[i]
        
print(len(d))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n = int(input())
al = []
for _ in range(n):
    a = int(input())
    al.append(-a)

def LIS(L):
  from bisect import bisect
  seq=[]
  for i in L:
    pos=bisect(seq,i)
    if len(seq)<=pos:
      seq.append(i)
    else:
      seq[pos]=i
  return len(seq)
  
print(LIS(al))

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = [-1]*N

for _ in range(N):
    val = int(input())
    n = bisect.bisect_left(A, val)
    A[n-1] = val

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

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
read = sys.stdin.read
readline = sys.stdin.readline


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

    a = [-1] * N

    for i in A:
        n = bisect_left(a, i)
        a[n - 1] = i

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

a = [-1] * N

for i in A:
    n = bisect_left(a, i)
    a[n - 1] = i

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from bisect import bisect
    n=int(input())
    A=[-int(input()) for _ in range(n)]
    B=[]
    for a in A:
        i=bisect(B,a)
        if(i==len(B)): B.append(a)
        else: B[i]=a
    print(len(B))
resolve()

Submission status: Accepted

Solution code:
import bisect

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

Q = [A[0]] + [0] * (n+1)
le = 1
for i in range(1, n):
    if Q[le-1] <= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        ind = bisect.bisect_right(Q, A[i], 0, le)
        Q[ind] = A[i]
    # print(Q[:10])

print(le)

Submission status: Accepted

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

Q = [-float("inf"), A[0]] + [float("inf")] * (n+1)
le = 2
for i in range(1, n):
    if Q[le-1] >= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        l = 0
        r = le
        m = (l+r)//2
        while r-l > 1:
            if Q[m] >= A[i]:
                l = m
            else:
                r = m
            m = (l+r)//2
        Q[l+1] = A[i]
    # print(Q[:10])

print(le-1)

Submission status: Accepted

Solution code:
import bisect

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


colors = []

#後ろから見ていく
for i,n in enumerate(list(reversed(A))):
    # 一つ目はとりあえずなんか一色ぬる
    if i == 0:
        colors.append(n)
    else:
        #二つ目以降は、各色の最小値のなかで、今見ているのより小さいものがあればそれを置き換える
        # 「各色の最小値集合の最小値と置き換える」を繰り返すので、最小値集合の最大より大きいなら最後に追加
        idx = bisect.bisect_right(colors, n)
        #if idx == len(colors):
        if colors[-1] <= n:
            colors.append(n)
        else:
            colors[idx] = n

print(len(colors))

Submission status: Accepted

Solution code:
import bisect

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


colors = []

#後ろから見ていく
for i,n in enumerate(list(reversed(A))):
    # 一つ目はとりあえずなんか一色ぬる
    if i == 0:
        colors.append(n)
    else:
        #二つ目以降は、各色の最小値のなかで、今見ているのより小さいものがあればそれを置き換える
        #ここをbisect_leftにすると、colorsの中で同じ最小値があるときにinsertが必要なので遅い
        # 「各色の最小値集合の最小値と置き換える」を繰り返すので、最小値集合の最大より大きいなら最後に追加
        idx = bisect.bisect_right(colors, n)
        if idx == len(colors):
            colors.append(n)
        else:
            colors[idx] = n

print(len(colors))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
l = [0 for i in range(n)]
for i in range(n):
    a1 = int(input())
    l[n-1-i] = a1
h = [l[0]]
ans = 1
for i in range(1,n):
    a = bisect.bisect_right(h,l[i])
    if ans == a:
        ans += 1
        h.append(l[i])
    else:
        h[a] = l[i]
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = [int(input())for i in range(N)]
m = [-A[0]]
ans = 1
for i in A[1:]:
    p = bisect.bisect_left(m,-i+1)
    if p == ans:
        ans += 1
        m.append(-i)
    else:
        m[p] = -i
print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
first = [-1 for _ in range(N)]
for a in A:
    i = bisect.bisect_left(first,a)
    first[i-1] = a
ctr = N
for f in first:
    if f == -1:
        ctr -= 1
print(ctr)

Submission status: Accepted

Solution code:
from collections import deque
import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
ans = int(0)

N = I()
color = []
a = I()
maxcolor =deque()
maxcolor.append(a)
lena = 1
for i in range(N-1):
    minmaxcolor = maxcolor[0]
    a = I()
    if a<=minmaxcolor:
        maxcolor.appendleft(a)
#        maxcolor.append(a)
        lena += 1
    else:
        acandi = bisect.bisect_left(maxcolor, a)
        maxcolor[acandi-1] = a
        """
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        
        for _ in range(aupper+1):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2
        """

#print(maxcolor)
ans = len(maxcolor)
print(ans)

Submission status: Accepted

Solution code:
import sys,bisect
input=sys.stdin.readline
n=int(input())

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

dp=[float("inf")]*(n+1)
for b in a:
    idx=bisect.bisect_right(dp,b)
    dp[idx]=b

ans=bisect.bisect_left(dp,float("inf"))

print(ans)

Submission status: Accepted

Solution code:
#LIS
n=int(input())
lists=[0]*n
for i in range(n):
    lists[i]=int(input())
import bisect
counter=0
lislist=[lists[-1]]
for i in range(2,n+1):
    a=lists[-i]
    index=bisect.bisect_right(lislist,a)
    if index<len(lislist):
        lislist[index]=a

    elif index==len(lislist):
        lislist.append(a)

print(len(lislist))

Submission status: Accepted

Solution code:
#LIS
n=int(input())
lists=[0]*n
for i in range(n):
    lists[i]=int(input())
import bisect
counter=0
lislist=[lists[-1]]
for i in range(2,n+1):
    a=lists[-i]
    index=bisect.bisect_right(lislist,a)
    if index<len(lislist):
        lislist[index]=a

    elif index==len(lislist):
        lislist.append(a)

print(len(lislist))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def LIS(seq,wider_sense = False):
    from bisect import bisect_left, bisect_right
    f = bisect_right if wider_sense else bisect_left
    N = len(seq)
    INF = 10**18
    dp = [INF] * (N+1)
    for x in seq:
        i = f(dp,x)
        dp[i] = x
    return f(dp,INF-1)

answer = LIS([-x for x in A],wider_sense=True)
print(answer)

Submission status: Accepted

Solution code:
import bisect

INF = 10000000000

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

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

dp = [INF] * n

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

Submission status: Accepted

Solution code:
# ABC134E - Sequence Decomposing
def longest_subsequence(A: "Array[int]", equals: bool, increasing: bool) -> int:
    from bisect import bisect_left, bisect_right

    bs = bisect_right if equals else bisect_left
    compare = (lambda x, y: x >= y) if equals else (lambda x, y: x > y)
    if not increasing:
        A = A[::-1]
    
    dp = [A[0]]  # dp := length of LIS (dp table itself is not LIS)
    for i in A[1:]:
        if compare(i, dp[-1]):
            dp.append(i)
        else:
            dp[bs(dp, i)] = i
    return len(dp)


def main():
    N, *A = map(int, open(0))
    ans = longest_subsequence(A, equals=1, increasing=0)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC134E - Sequence Decomposing
def lis(A: "Array[int]") -> int:
    from bisect import bisect_right

    # dp := length of LIS (dp table itself is not LIS)
    dp = [A[0]]
    for i in A[1:]:
        if i >= dp[-1]:
            dp.append(i)
        else:
            dp[bisect_right(dp, i)] = i
    return len(dp)


def main():
    N, *A = map(int, open(0))
    ans = lis(A[::-1])  # need the length of LDS -> reverse A
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


print(len(arr))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_right

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

def LIS(seq):
    # 狭義
    N = len(seq)
    INF = 10**18
    dp = [INF] * (N+1)
    for x in seq:
        i = bisect_right(dp,x)
        dp[i] = x
    return bisect_right(dp,INF-1)

answer = LIS([-x for x in A])
print(answer)

Submission status: Accepted

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

# 各色の最大数を保持
colors = deque()
for n in l:
    # 各色の最大数のどれよりも大きくなかったとき色を増やす
    ind = bisect.bisect_left(colors, n)
    if ind == 0:
        colors.appendleft(n)
    else:
        colors[ind-1] = n
print(len(colors))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
import bisect
from collections import deque
h=deque()
for i in range(n):
    idx=bisect.bisect_left(h,a[i])
    if idx==0:
        h.appendleft(a[i])
    else:
        h[idx-1]=a[i]

print(len(h))

Submission status: Accepted

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

de = deque([])
de.append(A[0])
for a in A[1:]:
    ind = bl(de, a)
    if ind == 0:
        de.appendleft(a)
    else:
        de[ind-1] = a

print(len(de))

Submission status: Accepted

Solution code:
#間違い
inf=float("inf")
from heapq import heappop,heappush 
n=int(input())
a=[int(input()) for _ in range(n)]
dp=[-1]*(n)
dp[0]=a[0]
for i in range(1,n):
    m=0
    M=n-1
    while M-m>1:
        if dp[(M+m)//2]<a[i]:
            M=(M+m)//2
        else:
            m=(M+m)//2
    if dp[m]>=a[i]:
        dp[M]=a[i]
    else:
        dp[m]=a[i]
count=0
for i in range(n):
    if dp[i]!=-1:
        count+=1
    else:
        break
print(count)

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n = int(input())
xs = [int(input()) for _ in range(n)]
d = {}
for i, x in enumerate(sorted(xs)):
    d[x] = i

segtree = SegTree([0]*n, n, 0, max)
r = 0
for x in xs:
    xi = d[x]
    y = segtree.query(xi, n)
    segtree.update(xi, y+1)
    r = max(r, y+1)
print(r)

Submission status: Accepted

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

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

Color = []
for a in A:
  idx = bisect.bisect_right(Color,a)
  if idx == len(Color):
    Color.append(a)
  else:
    Color[idx] = a
  #Color.sort()
  #print(Color)
print(len(Color))

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

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

q = deque([A[0]])

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

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
Q = [-a[0]]
for i in range(1,n):
    if a[i] <= -Q[-1]:
        Q.append(-a[i])
    else:
        j = bisect.bisect_right(Q,-a[i])###right
        #print(a,Q,i,j)
        Q[j] = -a[i]
    #print(i,Q)
print(len(Q))

Submission status: Accepted

Solution code:
from collections import*
from bisect import*
N,*A=map(int,open(0))
q=deque([A[0]])
for x in A[1:]:
	i=bisect_left(q,x)
	if i==0:q.appendleft(x)
	else:q[i-1]=x
print(len(q))

Submission status: Accepted

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

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

Submission status: Accepted

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




n = int(sys.stdin.readline())
L = [int(sys.stdin.readline()) for i in range(n)]
IS = deque([L[0]])
for i in range(1, n):
    if L[i] <= IS[0]:
        IS.appendleft(L[i])
    else:
        IS[bisect_left(IS, L[i]) - 1] = L[i]



print(len(IS))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = IR(n)
IS = deque([L[0]])
for i in range(1, n):
    if L[i] <= IS[0]:
        IS.appendleft(L[i])
    else:
        IS[bisect_left(IS, L[i]) - 1] = L[i]



print(len(IS))

Submission status: Accepted

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


def bi(a, x):
    i, j = 0, len(a) - 1
    while i != j:
        k = (i + j) // 2
        if a[k] >= x:
            i = k+1
        else:
            j = k
    if a[-1] >= x:
        i =-1
    return i


for i in a:
    j = bi(b, i)
    if j == -1:
        b.append(i)
        c += 1
    else:
        b[j] = i
print(c)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque
N = int(input())
ls = deque([])
ans = 0
for i in range(N):
  a = int(input())
  if ls:
    ID = bisect_left(ls, a)
    if ID==0:
      ans += 1
      ls.appendleft(a)
    else:
      ls[ID-1]= a
  else:
    ans += 1
    ls.append(a)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left

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

dp = [1]*N

for a in A:
    ia = bisect_right(dp, -a)
    if dp[ia] == 1:
        dp[ia] = -a
    else:
        ib = bisect_left(dp, -a+1)
        dp[ib] = -a
    #print(dp)

ans = 0
for i in range(N):
    if dp[i] != 1:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

N = int(input())

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

B = [A[0]]

for j in range(1,N):
    if B[-1] <= A[j]:
        B.append(A[j])
    else:
        B[bisect.bisect_right(B,A[j])] = A[j]
    #print(B)

print(len(B))

Submission status: Accepted

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

from bisect import *

h = []

for a in A:
    x = bisect_right(h, -a)
    if len(h) <= x:
        h.append(-a)
    else:
        h[x] = -a

result = len(h)

print(result)

Submission status: Accepted

Solution code:
#E問題
import heapq
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
A = A[::-1]

C = []
for i in range(N):
    if i == 0:
        C.append(A[i])
    else:
        li = bisect.bisect_right(C,A[i])
        if li == len(C):
            C.append(A[i])
        else:
            C[li] = A[i]
    
print(len(C))

Submission status: Accepted

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

for _ in range(n):
    a = int(input())
    if len(q) == 0:
        q.appendleft(a)
    elif a <= q[0]:
        q.appendleft(a)
    else:
        i = bisect.bisect_right(q, a-1) - 1
        q[i] = a
print(len(q))

Submission status: Accepted

Solution code:
import bisect
n=int(input())
h=[]
for i in range(n):
  a=int(input())
  if len(h)==0:
    h.append(-1*a)
  elif (-1)*a>=h[-1]:
    h.append(-1*a)
  else:
    index=bisect.bisect_right(h,-1*a)
    h[index]=-1*a
print(len(h))

Submission status: Accepted

Solution code:
class Multiset:
    def __init__(self, N):
        self.N = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def bisect(self, w):
        if w <= 0:
            return 0
        bit, N = self.tree, self.N
        i = 0
        for k in self.bisect_K:
            ni = i + k
            if ni <= N and bit[ni] < w:
                w -= bit[ni]
                i = ni
        return i + 1

    def insert(self, i):
        while i <= self.N:
            self.tree[i] += 1
            i += i & -i

    def erase(self, i):
        while i <= self.N:
            self.tree[i] -= 1
            i += i & -i

    def lower_bound(self, x):
        return self.bisect(self.sum(x))

    def size(self):
        return self.sum(self.N)


def main():

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

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

    memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
    M = len(memo)

    ms = Multiset(M)
    for b in (memo[a] for a in A):
        i = ms.lower_bound(b - 1)
        if i != 0:
            ms.erase(i)
        ms.insert(b)

    print(ms.size())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Multiset:
    def __init__(self, N):
        self.N = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.N:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        if w <= 0:
            return 0
        bit, N = self.tree, self.N
        i = 0
        for k in self.bisect_K:
            ni = i + k
            if ni <= N and bit[ni] < w:
                w -= bit[ni]
                i = ni
        return i + 1

    def insert(self, x):
        self.add(x, 1)

    def erase(self, x):
        self.add(x, -1)

    def lower_bound(self, x):
        return self.bisect(self.sum(x))

    def size(self):
        return self.sum(self.N)


def main():

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

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

    memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
    M = len(memo)

    ms = Multiset(M)
    for b in (memo[a] for a in A):
        i = ms.lower_bound(b - 1)
        if i != 0:
            ms.erase(i)
        ms.insert(b)

    print(ms.size())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        if w <= 0:
            return 0
        bit, N = self.tree, self.size
        i = 0
        for k in self.bisect_K:
            ni = i + k
            if ni <= N and bit[ni] < w:
                w -= bit[ni]
                i = ni
        return i + 1


class Multiset:
    def __init__(self, N):
        self.N = N
        self.bit = BIT(N)

    def insert(self, x):
        self.bit.add(x, 1)

    def erase(self, x):
        self.bit.add(x, -1)

    def lower_bound(self, x):
        return self.bit.bisect(self.bit.sum(x))

    def size(self):
        return self.bit.sum(self.N)

def main():

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

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

    memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
    M = len(memo)

    ms = Multiset(M)
    for b in (memo[a] for a in A):
        i = ms.lower_bound(b - 1)
        if i != 0:
            ms.erase(i)
        ms.insert(b)

    print(ms.size())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        if w <= 0:
            return 0
        bit, N = self.tree, self.size
        i = 0
        for k in self.bisect_K:
            if i + k <= N and bit[i + k] < w:
                i += k
                w -= bit[i]
        return i + 1


class Multiset:
    def __init__(self, N):
        self.N = N
        self.bit = BIT(N)

    def insert(self, x):
        self.bit.add(x, 1)

    def erase(self, x):
        self.bit.add(x, -1)

    def lower_bound(self, x):
        return self.bit.bisect(self.bit.sum(x))

    def size(self):
        return self.bit.sum(self.N)


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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

ms = Multiset(M)
for b in (memo[a] for a in A):
    i = ms.lower_bound(b - 1)
    if i != 0:
        ms.erase(i)
    ms.insert(b)

print(ms.size())

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        for k in self.bisect_K:
            if i + k <= N and bit[i + k] < w:
                i += k
                w -= bit[i]
        return i + 1


class Multiset:
    def __init__(self, N):
        self.N = N
        self.bit = BIT(N)

    def insert(self, x):
        self.bit.add(x, 1)

    def erase(self, x):
        self.bit.add(x, -1)

    def lower_bound(self, x):
        s = self.bit.sum(x)
        return self.bit.bisect(s) if s else 0

    def size(self):
        return self.bit.sum(self.N)


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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

ms = Multiset(M)
for b in (memo[a] for a in A):
    i = ms.lower_bound(b - 1)
    if i != 0:
        ms.erase(i)
    ms.insert(b)

print(ms.size())

Submission status: Accepted

Solution code:
import bisect
def main():

    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))
    B = [A[-1]]
    for i in range(N-2, -1, -1):
        if B[-1] <= A[i]:
            B.append(A[i])
        else:
            j = bisect.bisect_right(B, A[i])
            B[j] = A[i]
    return len(B)

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.bisect_K = [1 << k for k in reversed(range(N.bit_length()))]

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        for k in self.bisect_K:
            if i + k <= N and bit[i + k] < w:
                i += k
                w -= bit[i]
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

bit = BIT(M)
for b in (memo[a] for a in A):
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.MSB = 1 << (N.bit_length() - 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        K = N.bit_length()
        for k in (1 << k for k in reversed(range(K))):
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
M = len(memo)

bit = BIT(M)
for b in (memo[a] for a in A):
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))