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:
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 = self.MSB
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        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 = self.MSB
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    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.bisect_k = 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 __str__(self):
        return "BIT: [{}]".format(
            ", ".join(str(self.sum(i + 1) - self.sum(i))
                      for i in range(self.size))
        )

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        k = self.bisect_k
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    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)

    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 __str__(self):
        return "BIT: [{}]".format(
            ", ".join(str(self.sum(i + 1) - self.sum(i))
                      for i in range(self.size))
        )

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        k = 1 << (N.bit_length() - 1)
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        return i + 1

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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    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)

    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 __str__(self):
        return "BIT: [{}]".format(
            ", ".join(str(self.sum(i + 1) - self.sum(i))
                      for i in range(self.size))
        )

    def bisect(self, i):
        l, r = 0, i
        s = self.sum(r)
        if s == 0:
            return 0
        while r - l > 1:
            m = (r + l) // 2
            if self.sum(m) < s:
                l = m
            else:
                r = m
        return l + 1


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

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    i = bit.bisect(b - 1)
    if i != 0:
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Submission status: Accepted

Solution code:
from bisect import bisect_left as b
n=int(input())
p=[-1]*(n+1)
p[-1]=float("INF")
q=n
for i in range(n):
    x=int(input())
    d=b(p,x)-1
    q=min(q,d)
    p[d]=x
print(n-q)

Submission status: Accepted

Solution code:
import sys
import bisect

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

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

	return(len(l))

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

main()

Submission status: Accepted

Solution code:
from bisect import bisect_right
N = int(input())
dp = [float("inf") for _ in range(N+1)]

rows = 0
for _ in range(N):
    c = -float(input())
    i = bisect_right(dp, c)
    if i == rows:
        rows += 1
    dp[i] = c
print(len(list(filter(lambda x:x < float("inf"), dp))))

Submission status: Accepted

Solution code:
import bisect as b
from collections import deque
n=int(input())
ans=1
clist=deque([int(input())])
for i in range(n-1):
    next=int(input())
    pos=b.bisect_left(clist,next)
    if pos==0:
        clist.appendleft(next)
        ans+=1
    else:
        clist[pos-1]=next
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

A.reverse()

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

print(len(dp))

Submission status: Accepted

Solution code:
def se(c, x, h, l):
    if h == l:
        return l
    t = (h+l)//2
    if c[t] <= x:
        a = se(c,x,h,t+1)
    else:
        a = se(c,x,t,l)
    return a
        
    
import numpy as np
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
diff = np.diff(a)
tmp = np.sum(diff<=0)
if tmp == len(diff):
    print(len(a))
elif tmp == 0:
    print(1)
else:
    for i in a[::-1][1:]:
        if c[-1] <= i:
            c.append(i)
        else:
            c[se(c,i,len(c),0)] = i
    print(len(c))

Submission status: Accepted

Solution code:
import sys
import bisect

n = int(input())
a = [int(sys.stdin.readline().rstrip()) for _ in range(n)][::-1]

bottoms = [a[0]]

for i in range(1, n):
    pos = bisect.bisect_right(bottoms, a[i])
    if pos == len(bottoms):
        bottoms.append(a[i])
    else:
        bottoms[pos] = a[i]

print(len(bottoms))

Submission status: Accepted

Solution code:
import bisect
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)

Submission status: Accepted

Solution code:
from bisect import bisect

# n, k = 5, 4
n = int(input())
seq = []
for i in range(n):
	ele = int(input())
	pos = bisect(seq, -ele)
	if len(seq) <= pos:
		seq.append(-ele)
	else:
		seq[pos] = -ele 
print(len(seq))

Submission status: Accepted

Solution code:
import bisect
from collections import deque
N = int(input())
S = deque([int(input())])
for _ in range(N-1):
    a = int(input())
    ind = bisect.bisect_right(S,a)
    if S[ind-1]==a:
        ind1 = bisect.bisect_left(S,a)
        if ind1>0 and S[ind1-1]<a:
            S[ind1-1]=a
        else:
            S.appendleft(a)
    elif ind==0:
        S.appendleft(a)
    else:
        S[ind-1]=a
#     print("a,S = {}{}".format(a,S))
print(len(S))

Submission status: Accepted

Solution code:
from bisect import bisect

n = int(input())

seq = []
for i in range(n):
	ele = int(input())
	pos = bisect(seq, -ele)
	if len(seq) <= pos:
		seq.append(-ele)
	else:
		seq[pos] = -ele

print(len(seq))

Submission status: Accepted

Solution code:
#54 ABC134E

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

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

print(LIS(a))

Submission status: Accepted

Solution code:
import bisect

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

colors = []
max_val = -1 * (10 ** 10)
for num in nums:
	if num >= max_val:
		colors.append(num)
		max_val = num
	else:
		idx_r = bisect.bisect_right(colors, num)
		colors[idx_r] = num
		max_val = min(colors[-1], max_val)

print(len(colors))

Submission status: Accepted

Solution code:
import bisect

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

colors.append(arr[-1])
cnum = len(colors)
for a in arr[-2::-1]:
  i = bisect.bisect_right(colors, a)
  if i < cnum:
    colors[i] = a
  else:
    colors.append(a)
    cnum += 1

print(cnum)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    A = LIN(N)[::-1] #bisect使いたいので
    LIS = [A[0]] #もとの順序の広義単調減少は反転させた配列の広義単調増加
    for a in A[1:]:
        if LIS[-1] <= a:
            LIS.append(a)
        else:
            update_index = bisect_right(LIS,a)
            LIS[update_index] = a
    print(len(LIS))





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

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

ans = [-1] * n
for b in a:
    ans[bisect.bisect(ans, b-1) - 1] = b

print(n - bisect.bisect(ans, -1))

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline  #文字列入力では注意！

def main():
        #ttps://atcoder.jp/contests/abc134/submissions/6459172
    from bisect import bisect
    import sys
    input = sys.stdin.readline
    n = int(input())
    A = [int(input()) for _ in range(n)]
    dp = [1]
    for a in A:
        a *= -1
        i = bisect(dp,a)   #既存に-aを挿入した時のindex

        if i < len(dp):    #挿入位置が長さより小さい時（要はabsが一番小さくない時
            dp[i] = a     #-aにする
        else:
           dp.append(a)    #右端に-aを普通に追加

    print(len(dp))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#ttps://atcoder.jp/contests/abc134/submissions/6459172
from bisect import bisect
import sys
input = sys.stdin.readline
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1]
for a in A:
    a *= -1
    i = bisect(dp,a)   #既存に-aを挿入した時のindex

    if i < len(dp):    #挿入位置が長さより小さい時（要はabsが一番小さくない時
        dp[i] = a     #-aにする
    else:
        dp.append(a)    #右端に-aを普通に追加


print(len(dp))

Submission status: Accepted

Solution code:
#ttps://atcoder.jp/contests/abc134/submissions/6459172
from bisect import bisect
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1]
for a in A:
    a *= -1
    i = bisect(dp,a)   #既存に-aを挿入した時のindex

    if i < len(dp):    #挿入位置が長さより小さい時（要はabsが一番小さくない時
        dp[i] = a     #-aにする
    else:
        dp.append(a)    #右端に-aを普通に追加


print(len(dp))

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
N = int(input())
inf = 10 ** 9 + 1
lis = [inf] * (N + 1)
res = 0
for _ in range(N):
  a = -int(input())
  ind = br(lis, a)
  if a <= lis[ind]:
    lis[ind] = a

for i in range(1, N + 1):
  if lis[i] == inf:
    break
  res = i
print(res + 1)

Submission status: Accepted

Solution code:
def main():
    import sys
    import bisect
    import collections
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for i in range(N)]
    tmp = collections.deque()
    for i in range(N):
        insert_index = bisect.bisect_left(tmp,A[i])
        if insert_index == 0:
            tmp.appendleft(A[i])
        else:
            tmp[insert_index-1] = A[i]
    answer = len(tmp)
    print(answer)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

A = []
for _ in range(N):
    a = int(input())
    A.append(a)
    
nums = A[:]
colors = [float('inf')] * N

from bisect import bisect_left, bisect_right, insort_right
ans = 0
for n in nums:
    idx = bisect_right(colors, -n)
    colors[idx] = -n
    #print(ans)
    if idx > ans:
        ans = idx
    #print(idx, colors)
            
print(ans+1)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]

dq = deque([a[0]])
for i in range(1, n):
    idx = bisect_left(dq, a[i])
    if idx == 0:
        dq.appendleft(a[i])
    else:
        dq[idx-1] = a[i]

print(len(dq))

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]

x = [float('inf') for _ in range(n)]
for i in range(n)[::-1]:
    r = bisect.bisect_right(x,a[i])
    x[r] = a[i]
cnt = x.count(float('inf'))
print(n-cnt)

Submission status: Accepted

Solution code:
from bisect import *

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

inf = float('inf')
ret = [inf] * N

ind = 0
for elem in A:
    i = bisect_right(ret, elem)
    ret[i] = elem
    if ind < i:
        ind = i

print(ind+1)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

min_stack = [a[-1]]

for i in range(2,n+1):
    if min_stack[-1] <= a[-i]:
        min_stack.append(a[-i])
    else:
        tmp = min_stack[bisect_left(min_stack, a[-i])]
        if tmp == a[-i]:
            min_stack[bisect_left(min_stack, a[-i]+1)] = a[-i]
        else:
            min_stack[bisect_left(min_stack, a[-i])] = a[-i]

print(len(min_stack))

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

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

from bisect import bisect_left

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

val = [-1]*N
for i in range(N):
    temp = bisect_left(val,A[i])
    val[temp-1] = A[i]

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

print(ans)

Submission status: Accepted

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

N = int(stdin.readline().rstrip())
A = [int(stdin.readline().rstrip()) for _ in range(N)]

colors = deque([10 ** 10])
for i in range(N):
    bi = bisect.bisect_left(colors, A[i])
    bir = bisect.bisect_right(colors, A[i])
    if bir == len(A):
        colors[len(A) - 1] = A[i]
    elif bi == 0:
        colors.appendleft(A[i])
    else:
        colors[bi - 1] = A[i]

print(len(colors) - 1)

Submission status: Accepted

Solution code:
from bisect import *


def p_e():
    N = int(input())
    # A = [int(input()) for _ in range(N)]
    ans = [-1] * N

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

    print(N - bisect(ans, -1))


if __name__ == '__main__':
    p_e()

Submission status: Accepted

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

from bisect import bisect_left
from collections import deque

def main():
  N = int(input())
  liA = list(map(int, [input() for _ in range(N)]))
  colors = deque([liA[0]])
  for a in liA[1:]:
    if a <= colors[0]:
      colors.appendleft(a)
    else:
      i = bisect_left(colors, a)
      colors[i-1] = a

  print(len(colors))
  pass

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from bisect import *
n = int(input())
a = [int(input()) for i in range(n)]

color = [-a[0]]
for i in range(1,n):
    if -a[i] >= color[-1]:
        color.append(-a[i])
    else:
        idx = bisect_right(color,-a[i])
        color[idx] = -a[i]

print(len(color))

Submission status: Accepted

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

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

li = [a[0]]
ans = 1

for i in range(1,n):
    if li[0] < a[i]:
        li[0] = a[i]
    elif li[-1] >= a[i]:
        li.append(a[i])
    else:
        p = 0
        q = len(li) - 1
        while p != q:
            c = (p + q) // 2
            if li[c] >= a[i]:
                p = c + 1
            else:
                q = c
        li[p] = a[i]

print(len(li))

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:
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]

dp = [float('inf')]*n
for i in range(n):
    x = bisect.bisect_right(dp,-a[i])
    dp[x] = -a[i]
c = dp.count(float('inf'))
print(n-c)

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
a = [int(input()) for _ in range(n)]
dp = [float('inf')]*n
for i in range(n):
    x = bisect.bisect_right(dp,-a[i])
    dp[x] = -a[i]
c = dp.count(float('inf'))
print(n-c)

Submission status: Accepted

Solution code:
from bisect import bisect_right
def solve(n, a):
    ans = 1
    L = [-a[0]]
    for i in range(1, n):
        x = -a[i]
        if x >= L[-1]:
            ans += 1
            L.append(x)
        else:
            L[bisect_right(L, x)] = x
    return ans

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

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

b = []

ans = 1
b.append(a[n-1])

for i in range(n-2, -1, -1):
    if a[i] >= b[-1]:
        b.append(a[i])
    else:
        x = bisect_right(b,a[i])
        b[x] = a[i]
        x -= 1
        while x >= 0:
            if b[x] > b[x+1]:
                b[x],b[x+1] = b[x+1],b[x]
                x -= 1
            else:
                break
    #print(b)

print(len(b))

Submission status: Accepted

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

num_col = 1
L = [-1*Alist[0]] 
for ai in Alist[1:]:
    #print(L)
    ai =-1*ai
    if ai >= L[-1]:
        L.append(ai)
        num_col += 1
    else:
        L[bisect_right(L, ai)] = ai
print(num_col)

Submission status: Accepted

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


dp = []
for a in A:
    i = bisect.bisect_right(dp, a)
    if i >= len(dp):
        dp.append(a)
    else:
        dp[i] = a

print(len(dp))

Submission status: Accepted

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

N = int(input())

columns = []


for _ in range(N):
    current = -int(input())
    index = bisect_right(columns, current)
    if len(columns) <= index:
        columns.append(current)
    else:
        columns[index] = current

print(len(columns))

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(1, N):

    index = bisect.bisect_right(now, -A[i])
    if index == len(now):
        now.append(-A[i])
    else:
        now[index] = -A[i]

print(len(now))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.append(-int(input()))
dp=[10**10 for i in range(n+1)]
import bisect
for i in a:
    idx=bisect.bisect_right(dp,i)
    dp[idx]=i

ans=bisect.bisect_left(dp,10**10)
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

LIS = [a[-1]]
for i in range(n - 2, -1, -1):
    if a[i] >= LIS[-1]:
        LIS.append(a[i])
    else:
        LIS[bisect.bisect_right(LIS, a[i])] = a[i]

print(len(LIS))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = []
for i in range(n):
    temp = int(input())
    a.append(temp)
a.reverse()
b = [a[0]]
counter = 1
for i in range(1,n):
    if a[i] >= b[-1]:
        counter += 1
        b.append(a[i])
    else:
        ind = bisect.bisect_right(b,a[i])
        b[ind] = a[i]
print(counter)

Submission status: Accepted

Solution code:
N = int(input())
L = []
from bisect import bisect_right
for _ in range(N):
    u = -int(input())
    index = bisect_right(L,u)
#    print(index)
    if index == len(L):
        L.append(u)
    else:
        L[index ] = u
print(len(L))

Submission status: Accepted

Solution code:
from collections import deque
import bisect

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

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

for a in A[1:]:
  if a <= ans[0]:
    ans.appendleft(a)
  elif a > ans[-1]:
    ans[-1] = a
  else:
    i = bisect.bisect_left(ans, a)
    ans[i - 1] = a

print(len(ans))

Submission status: Accepted

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

N = int(input())
l = [-int(input())]

for i in range(N-1):
  ai = -int(input())
# 各色の最大値がlの要素になるようにリストを拡大させていく
  if l[-1] <= ai:
    l.append(ai)
  else:
    b = bisect_right(l, ai)
    l[b] = ai
    
print(len(l))

Submission status: Accepted

Solution code:
import bisect
inf = 1000000009
n = int(input())
a = [int(input()) for i in range(n)]
b = [inf] * (n + 10)
for i in range(n):
    j = bisect.bisect_right(b, -a[i], 0, hi = len(b))
    b[j] = -a[i]
print(bisect.bisect_left(b, inf, 0, hi = len(b)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
from itertools import accumulate
from collections import Counter
from heapq import heappop, heappush
from bisect import bisect, bisect_left
import sys

input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))


class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.node = [0]*(self.size + 1)
 
    def initialize(self, S):
        # S[0] = 0にしておく
        # 1-indexed
        if len(S) < self.size + 1:
            S += [S[-1]] * (self.size+1 - len(S))
        for i in range(1, self.size+1):
            self.node[i] = S[i] - S[i - (i&-i)]
 
    def sum(self, i):
        res = 0
        while i:
            res += self.node[i]
            i -= (i & -(i))
        return res
 
    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.node[i] += x
            i += (i & -(i))
 
    def bisect_left(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] < x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1
 
    def bisect(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] <= x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1


class DammySet:

    def __init__(self, counter, INF=2**32, counter_is_unique_and_sorted=True, filled=1):
        if not counter_is_unique_and_sorted:
            if type(counter) != Counter:
                counter = Counter(counter)

            self.bit = BIT(len(counter.keys())+3)
            self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
            self.val = [counter[k] for k in self.key]
            S = list(accumulate(self.val))
            self.bit.initialize(S)

        else:
            self.bit = BIT(len(counter) + 3)
            self.key = [-INF] * (len(counter) + 3)
            self.key[-1] = INF
            self.val = [0] * (len(counter) + 3)
            for i in range(2, len(counter)+2):
                self.key[i] = counter[i-2]
                self.val[i] = filled

            if filled:
                S = [0] * (len(counter) + 3)
                for i in range(2, len(counter)+2):
                    S[i] = i-1
                S[-1] = len(counter)
                self.bit.initialize(S)

    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)

    def delete(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, -1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)

    def find_lt(self, v):
        #'Find rightmost value less than x'
        rk = bisect_left(self.key, v) - 1
        rs = self.bit.sum(rk)
        return self.bit.bisect_left(rs)


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = self.bit.bisect_left(tv)
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N = int(input())
A = [int(input()) for _ in range(N)]
C = sorted(set(A))
dset = DammySet(C, filled=0)
L =  len(dset.bit.node) - 1

for i in range(N):
    ix = dset.find_lt(A[i])
    if ix > 1:
        dset.bit.add(ix, -1)
    dset.add(A[i])

print(dset.bit.sum(L))