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: Time Limit Exceeded

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

cnt = 0
n = len(a)
#print(a)
while n > 0:
    cnt += 1
    cur = a.pop(0)
    i = 0
    n -= 1
    while i < n:
        #print(i, n, a)
        #print(cur, a[i])
        if cur < a[i]:
            cur = a.pop(i)
            n -= 1
            #print("cur", cur)
        else:
            i += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
top = [-1]
col = 1
for i in range(n):
    a = int(input())
    if top[-1] < a:
        top[-1] = a
    else:
        flag = True
        for i in range(1,col+1):
            if top[-i] < a:
                top[-i] = a
                flag = False
                break
        if flag:
            top.append(a)
            col += 1

# print(top)
print(col)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ans = []
ans.append(int(input()))

for i in range(n - 1):
    t = int(input())
    ch = 0
    for j in range(len(ans)):
        if t > ans[j]:
            ans[j] = t
            ch += 1
            break
    if ch == 0:
        ans.append(t)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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


b = []

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b = [ai] + b
        else:
            index = bisect.bisect_left(b, ai)
            b[index-1] = ai

print(len(b))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[-1]
for _ in range(n):
    x=int(input())
    if a[-1]>=x:
        a.append(x)
    else:
        for i in range(len(a)):
            if a[i]<x:
                a[i]=x
                break
    a.sort(reverse=True)
print(len(a))

Submission status: Time Limit Exceeded

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 = []
for i in range(N):
	loc = bisect.bisect_left(B, A[i])
	if loc == 0:
		B = [A[i]] + B
	else:
		B[loc - 1] = A[i]

print(len(B))

Submission status: Time Limit Exceeded

Solution code:
n=input()
arr=[]
ma=[]
l=0
for _ in range(n):
    x=input()
    if len(ma)==0:
        ma.append(x)
        l+=1
    else:
        fg=True
        for i in range(len(ma)):
            if ma[i]<x:
                ma[i]=x
                fg=False
                break
        if fg:
            ma.append(x)
            l+=1
            ma.sort(reverse=True)
print l

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
top = [-1]
col = 1
for i in range(n):
    a = int(input())
    if top[-1] < a:
        top[-1] = a
    else:
        flag = True
        for i in range(1,col+1):
            if top[-i] < a:
                top[-i] = a
                flag = False
        if flag:
            top.append(a)
            col += 1

# print(top)
print(col)

Submission status: Time Limit Exceeded

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

last_nums=[-1]*N


for i in range(N):
    if len(last_nums) == 0:
        last_nums.append(A[i])
    else:
        for j in range(N):
            if A[i] > last_nums[j]:
                last_nums[j] = A[i]
                break

ans = 0
for num in last_nums:
    if num >= 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    _ = int(input())
    A = list(map(int, sys.stdin.readlines()))
    
    arr = [A[0]]
    for a in A[1:]:
        for i in range(len(arr)):
            if a > arr[i]:
                arr[i] = a
                break
        else:
            arr.append(a)
    print(len(arr))
    
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    
    L = [A.pop(0)]
    ma = L[0]
    for a in A:
        if ma >= a:
            ma = a
            L.append(ma)
            continue
        for i, l in enumerate(L):
            if l < a:
                L[i] = a
                ma = min(L)
                break
        else:
            L.append(a)
    return len(L)


def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))

    # N = 10**5
    # A = [random.randint(1, 10**9) for _ in range(N)]
    # # A.sort()
    # # A.reverse()
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())

largest = []
for i in range(N):
    A_i = int(input())
    idx = bisect.bisect_left(largest, A_i)
    if idx == 0:
        largest.insert(0, A_i)
    else:
        largest[idx - 1] = A_i
print(len(largest))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0
while a:
    b = a[:]
    for i in range(len(a)):
        if i == 0:
            b.remove(a[i])
        elif a[i] > a[i-1]:
            b.remove(a[i])
    ans += 1
    a = b

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def bi(l,x):
    ok = len(l)
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
        t.sort(reverse=True) 
print(m)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
seq = []
colors = []
for i in range(n):
    num = int(input())
    seq.append(num)
    if i == 0:
        colors.append([num])
    else:
        curr = 0
        append = False
        while not append and curr < len(colors):
            #print("hel")
            if num > colors[curr][-1]:
                colors[curr].append(num)
                append = True
            else:
                curr += 1
        if append == False and curr == len(colors):
            colors.append([num])
print(len(colors))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left


def solve():
  N = int(input())
  An = [int(input()) for _ in range(N)]
  if N==1:
    return 1
  else:
    ret = [An[0]]
    for a in An[1:]:
      idx = bisect_left(ret,a)
      if idx == 0:
        ret = [a] + ret
      else:
        ret[idx-1] = a
    return len(ret)


print(solve())

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=[int(input()) for _ in range(n)]
ans=0
while 1:
  tmp=[]
  if len(arr)==0:
    break
  val=arr[0]
  for i in range(1,len(arr)):
    if arr[i]>val:
      val=arr[i]
    else:
      tmp.append(arr[i])
  arr=tmp
  ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
b=[int(input()) for i in range(a)]
c=[]
for i in range(a):
  d=0
  for j in range(len(c)):
    if b[i]>c[j]:
      d=1
      c[j]=b[i]
      break
  if d==0:
    e=b[i]
    c.append(e)    
print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def myinput_int():
    return list(map(int, input().split()))

N, = myinput_int()

now=np.ones(100000)*-1
for i in range(N):
    temp, = myinput_int()
    now[np.where(now<temp)[0][0]]=temp
    now = np.sort(now)[::-1]

print(len(np.where(0<=now)[0]))

Submission status: Time Limit Exceeded

Solution code:
import heapq


def main():
    n = input()
    aa = []
    for _ in xrange(n):
        aa.append(input())
    xx = [aa.pop()]
    buf = []
    while aa:
        a = aa.pop()
        if a < xx[0]:
            heapq.heapreplace(xx, a)
        else:
            while xx and a >= xx[0]:
                heapq.heappush(buf, heapq.heappop(xx))
            if xx:
                heapq.heapreplace(xx, a)
                for b in buf:
                    heapq.heappush(xx, b)
                buf = []
            else:
                heapq.heappush(buf, a)
                xx = buf
                buf = []
    print len(xx)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    N = int(input())
    A = list(map(int, sys.stdin.readlines()))
    
    arr = [A[0]]
    for a in A[1:]:
        for i in range(len(arr)):
            if a > arr[i]:
                arr[i] = a
                break
        else:
            arr.append(a)
        arr.sort(reverse=True)
    print(len(arr))
    
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

l = deque()

for a in A:
    if len(l) == 0:
        l.append(a)
    else:
        tmp_deque = deque()
        while len(l) > 0:
            num = l.popleft()
            if num >= a:
                tmp_deque.append(num)
            else:
                break
        tmp_deque.append(a)
        l.extendleft(tmp_deque)
        

print(len(l))

Submission status: Time Limit Exceeded

Solution code:
N = input()
N = int(N)
S = [int(input()) for _ in range(N)]
result = 0

for i in range(N):
    if S[i] >= 0:
        result += 1
        hoge = S[i]
        for j in range(i+1,N):
            if S[j] > hoge and hoge != -1:
                hoge = S[j]
                S[j] = -1 
print(result)

Submission status: Time Limit Exceeded

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

cnt=0
L=[]
for i in range(N):
    n=int(input())
    L.append(n)
#print(L)
Q=[-1,10**10]
for i in range(N):
    if bisect.bisect_left(Q,L[i])==1:
        Q.insert(1,L[i])
    #elif bisect.bisect_left(Q,L[i])==len(Q)-1:
        #Q.insert(len(Q)-1,L[i])
    else:
        Q[bisect.bisect_left(Q,L[i])-1]=L[i]
    #print(Q)
print(len(Q)-2)

Submission status: Time Limit Exceeded

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

last_nums=[]


for i in range(N):
    if len(last_nums) == 0:
        last_nums.append(A[i])
    else:
        can_add = False
        for j in range(len(last_nums)):
            if A[i] > last_nums[j]:
                last_nums[j] = A[i]
                can_add = True
                break
        if can_add == False:
            last_nums.append(A[i])

print(len(last_nums))

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())

prevs = []

for i in range(N):
  val = int(input())
  insert_index = bisect.bisect_left(prevs, val)
  
  if (insert_index == 0):
    prevs.insert(insert_index, val)
  else:
    prevs[insert_index - 1] = val
    
print(len(prevs))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
lst = [10 ** 10]

for i in range(N):
	new_num = int(input())
	if new_num <= lst[0]:
		lst.insert(0,new_num)
	else:
		j = 0
		while lst[j] <= new_num:
			j += 1
		lst[j - 1] = new_num
				
print(len(lst) - 1)

Submission status: Time Limit Exceeded

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

cnt=0
L=[]
for i in range(N):
    n=int(input())
    L.append(n)
#print(L)
Q=[-1,10**10]
for i in range(N):
    if bisect.bisect_left(Q,L[i])==1:
        Q.insert(1,L[i])
    #elif bisect.bisect_left(Q,L[i])==len(Q)-1:
        #Q.insert(len(Q)-1,L[i])
    else:
        Q[bisect.bisect_left(Q,L[i])-1]=L[i]
    #print(Q)
print(len(Q)-2)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())

arr = []

for i in range(N):
    a = int(input())
    if len(arr) == 0:
        arr.append(a)
        continue

    index = bisect.bisect_left(arr, a)

    if arr[index - 1] < a:
        arr[index - 1] = a
    else:
        bisect.insort_right(arr, a)

print(len(arr))

Submission status: Time Limit Exceeded

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 = [0]*N
num = 0
color = 0
while True:
	value = -1
	for i in range(N):
		if B[i] == 0 and value < A[i]:
			value = A[i]
			B[i] = 1
			num += 1

	color += 1
	if num == N:
		break
print(color)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n = int(input())
ans = [int(input())]
for i in range(n-1):
    now = int(input())
    j = bisect_left(ans,now)
    if j == 0:
        ans = [now] + ans
    else:
        ans[j-1] = now

print(len(ans))

Submission status: Time Limit Exceeded

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

now_col = []

for i in range(n):
    now_k = -1
    now_v = -1
    for k, v in enumerate(now_col):
        if now_v < v < a[i]:
            now_v = v
            now_k = k
    if now_k != -1:
        now_col[now_k] = a[i]
    else:
        now_col.append(a[i])

print(len(now_col))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
lines = []
for i in range(N):
  curr = int(input())
  insertIndex = -1
  lineMax = -1
  for idx, lineA in enumerate(lines):
    if lineA < curr:
      if lineMax < lineA:
        lineMax = lineA
        insertIndex = idx
  if insertIndex < 0:
    lines.append(curr)
  else:
    lines[insertIndex] = curr

print(len(lines))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print(3*n**2)
    return

#B
def B():
    n,d = LI()
    f = [1]*(n+2*d+2)
    ans = 0
    for i in range(n):
        if f[i]:
            for j in range(i,i+2*d+1):
                f[j] = 0
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    a = IR(n)
    mi = max(a)
    if a.count(mi) > 1:
        for i in range(n):
            print(mi)
    else:
        b = [a[i] for i in range(n)]
        b.sort()
        b = b[::-1]
        for i in range(n):
            if mi != a[i]:
                print(mi)
            else:
                print(b[1])

    return

#D
def D():
    n = I()
    a = LI()
    b = [0]*(n+1)
    for i in range(1,n+1)[::-1]:
        j = 2*i
        k = 0
        while j <= n:
            k ^= b[j]
            j += i
        if a[i-1]^k:
            b[i] = 1
    ans = []
    for i in range(n+1):
        if b[i]:
            ans.append(i)
    print(len(ans))
    if ans:
        print(*ans)
    return

#E
def E():
    n = I()
    a = IR(n)
    f = [1]*n
    for j in range(n+1):
        if sum(f) == 0:
            break
        mi = -1
        for i in range(n):
            if f[i]:
                if mi < a[i]:
                    mi = a[i]
                    f[i] = 0
    print(j)
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

color = []

for _ in range(N):
    a = int(input())
    b = False
    for i, c in enumerate(color):
        if a > c:
            color[i] = a
            b = True
            break
    if not b:
        color += [a]

print(len(color))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

dp = [-1]
for a in aaa:
    for i, m in enumerate(dp):
        if m < a:
            dp[i] = a
            break
    else:
        dp.append(a)
print(len(dp))

Submission status: Time Limit Exceeded

Solution code:
#

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    al = [int(input()) for _ in range(n)]

    lsbs = []
    for a in al:
        if len(lsbs) == 0:
            lsbs.append([a])
        else:
            added = False
            for lsb in lsbs:
                if lsb[-1] < a:
                    lsb.append(a)
                    added = True
                    break
            if not added:
                lsbs.append([a])
    print(len(lsbs))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def bisect_right_rev(lst, x):
    if lst[0] < x:
        return 0
    if x <= lst[-1]:
        return len(lst)

    a = 0
    b = len(lst) - 1

    while abs(b - a) > 1:
        c = (a + b) // 2

        if lst[c] < x:
            b = c
        else:
            a = c
    
    return b

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

for i in range(N):
    if len(seq) == 0:
        seq.append(A[i])
    else:
        ind = bisect_right_rev(seq, A[i])
        if ind == len(seq):
            seq.append(A[i])
        else:
            seq[ind] = A[i]

print(len(seq))

Submission status: Accepted

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

    print(len(LIS))


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

Submission status: Accepted

Solution code:
import bisect

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

A.reverse()

dp = [A[0]]

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

print(len(dp))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def bisect_right_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番右側のidx+1となる。
    '''
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

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

multi_lis = []
for a_i in A:
    if not multi_lis:
        multi_lis.append(a_i)
        continue

    if a_i <= multi_lis[-1]:
        multi_lis.append(a_i)
    else:
        p = bisect_right_reverse(multi_lis, a_i)
        multi_lis[p] = a_i 

print(len(multi_lis))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# E - Sequence Decomposing
import sys 
from bisect import bisect_right

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,read().split()))
X = [-1]*N
for a in A:
    i = bisect_right(X,a-1)-1
    X[i] = a
print(N - X.count(-1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# E - Sequence Decomposing
import sys 
from bisect import bisect_left
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,read().split()))


INF = 10**31
q = deque([])

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

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

lst = [a[0]]
for aa in a[1:]:
    i = bisect_right(lst, aa)
    if i == len(lst): lst.append(aa)
    else: lst[i] = aa

print(len(lst))

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

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

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

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

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

Submission status: Accepted

Solution code:
from collections import deque
import bisect

N = int(input())
table = deque()
for n in range(N):
    a = int(input())
    if n == 0:
        table.append(a)
    else:
        if a <= table[0]:
            table.appendleft(a)
        else:
            table[bisect.bisect_left(table, a)-1] = a
            
print(len(table))

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
N=int(input())
A=[int(input()) for _ in [0]*N]
def bl3(A,x):
    # Aは逆順ソートされている
    # x未満のうち最大の要素のインデックスを返す
    ok=len(A)
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if A[mid]<x:
            ok=mid
        else:
            ng=mid
    return ok

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

Submission status: Accepted

Solution code:
code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libcpp.utility cimport pair
from libcpp.string cimport string
from libcpp.vector cimport vector
from cython.operator cimport dereference
from libcpp cimport bool
from cython.operator cimport preincrement
from libc.stdio cimport getchar, printf
from cython.operator cimport predecrement
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld ", l[i])
cdef extern from "<set>" namespace "std" nogil:
    cdef cppclass multiset[T]:
        ctypedef T value_type
        cppclass iterator:
            T& operator*()
            iterator operator++()
            iterator operator--()
            bint operator==(iterator)
            bint operator!=(iterator)
        cppclass reverse_iterator:
            T& operator*()
            iterator operator++()
            iterator operator--()
            bint operator==(reverse_iterator)
            bint operator!=(reverse_iterator)
        cppclass const_iterator(iterator):
            pass
        cppclass const_reverse_iterator(reverse_iterator):
            pass
        multiset() except +
        multiset(multiset&) except +
        iterator begin()
        reverse_iterator rbegin()
        size_t count(const T&)
        bint empty()
        iterator end()
        reverse_iterator rend()
        iterator find(T&)
        size_t size()
        iterator upper_bound(const T&)
        iterator lower_bound(T&)
        pair[iterator, bint] insert(const T&) except +
        iterator erase(iterator)

cdef extern from *:
    ctypedef long long ll "long long"


cdef class MultiSet:
    cdef multiset[ll] *_thisptr
    def __cinit__(self):
        self._thisptr = new multiset[ll]()
    cpdef int size(self):
        return self._thisptr.size()
    cpdef bool empty(self):
        return self._thisptr.empty()
    cpdef void add(self, ll x):
        self._thisptr.insert(x)
    cpdef void remove(self, ll x):
        self._thisptr.erase(self._thisptr.find(x))
    cpdef int count(self, ll x):
        return self._thisptr.count(x)
    cpdef ll min(self):
        return dereference(self._thisptr.begin())
    cpdef ll max(self):
        return dereference(self._thisptr.rbegin())
    def lower_bound(self, x):
        cdef multiset[ll].iterator itr = self._thisptr.lower_bound(x)
        if itr == self._thisptr.end():
            return None
        else:
            return dereference(itr)
    def upper_bound(self, ll x):
        cdef multiset[ll].iterator itr = self._thisptr.upper_bound(x)
        if itr == self._thisptr.end():
            return None
        else:
            return dereference(itr)
    def next(self, x):
        if x >= self.max():
            return None
        cdef multiset[ll].iterator itr = self._thisptr.find(x)
        cdef int c = self._thisptr.count(x)
        for i in range(c):
            preincrement(itr)
        return dereference(itr)
    cpdef prev(self, x):
        if x <= self.min():
            return None
        cdef multiset[ll].iterator itr = self._thisptr.find(x)
        predecrement(itr)
        return dereference(itr)
    cpdef ll pop_min(self):
        cdef multiset[ll].iterator itr = self._thisptr.begin()
        cdef ll ret = dereference(itr)
        self._thisptr.erase(itr)
        return ret
    cpdef ll pop_max(self):
        cdef multiset[ll].reverse_iterator itr = self._thisptr.rbegin()
        cdef ll ret = dereference(itr)
        self._thisptr.erase(self._thisptr.find(ret))
        return ret
    def __contains__(self, x):
        if self._thisptr.find(x)==self._thisptr.end():
            return False
        else:
            return True
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import MultiSet, ReadInt

def main():
    ms = MultiSet()
    N = ReadInt(1)[0]
    for i in range(N):
        A = ReadInt(1)[0]
        if ms.empty():
            ms.add(A)
            continue
        if A <= ms.min():
            ms.add(A)
        else:
            b = ms.lower_bound(A)
            if b is None:
                ms.pop_max()
                ms.add(A)
            else:
                c = ms.prev(b)
                ms.remove(c)
                ms.add(A)
    print(ms.size())

if __name__ == "__main__":
    main()

Submission status: Accepted

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


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = [int(input()) for _ in range(n)]
    pile = deque()
    for i in range(n):
        index = bisect_left(pile, a[i])
        if index == 0:
            pile.appendleft(a[i])
        else:
            pile[index - 1] = a[i]
    print(len(pile))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right

def main():
    inf=float("inf")
    n=int(input())
    alst=[int(input()) for _ in range(n)]
    work=[inf]*n
    for i in range(n-1,-1,-1):
        j=bisect_right(work,alst[i])
        work[j]=alst[i]
    print(n-work.count(inf))

main()

Submission status: Accepted

Solution code:
import sys
import bisect

input = sys.stdin.readline
N = int(input())
A = [int(input()) for _ in range(N)]
# - bisect_right(=bisect)(iter, x): (iter[i] < x)を満たす最小のiを返す
# - bisect_left: (iter[i] <= x)を満たす最小のiを返す
c = []
for a in A:
    a *= -1
    i = bisect.bisect_right(c, a)
    if i == len(c):
        c.append(a)
    else:
        c[i] = a
print(len(c))

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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

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

for i in range(1, N):
    ind = bisect.bisect_left(dp, A[i])

    if ind == 0:
        dp.appendleft(A[i])
    # elif dp[-1] < A[i]:
    #     dp[-1] = A[i]
    else:
        dp[ind-1] = A[i]

print(len(dp))

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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

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

for i in range(1, N):
    ind = bisect.bisect_left(dp, A[i])

    if ind == 0:
        dp.appendleft(A[i])
    elif dp[-1] < A[i]:
        dp[-1] = A[i]
    else:
        dp[ind-1] = A[i]

print(len(dp))

Submission status: Accepted

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

color = [0] * (n+1)
for i in range(n):
    a = int(input())
    j = bisect_right(color, a)
    color[j-1] = a+1

ans = 0
for t in color:
    if t != 0:
        ans += 1

print(ans)