Problem:


Score : 500 points

Problem Statement

You are given a sequence with N integers: A = \{ A_1, A_2, \cdots, A_N \}.
For each of these N integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:

If A_i and A_j (i < j) are painted with the same color, A_i < A_j.

Find the minimum number of colors required to satisfy the condition.

Constraints

1 \leq N \leq 10^5

0 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the minimum number of colors required to satisfy the condition.

Sample Input 1

5
2
1
4
5
3

Sample Output 1

2

We can satisfy the condition with two colors by, for example, painting 2 and 3 red and painting 1, 4, and 5 blue.

Sample Input 2

4
0
0
0
0

Sample Output 2

4

We have to paint all the integers with distinct colors.



Sample input:
5
2
1
4
5
3


Sample output:
2

Submission status: Accepted

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

n = int(input())
colors_maxs = []

colors_maxs.append(int(input()) *(-1) )
for _ in range(n-1):
    a = int(input()) * (-1)
    if colors_maxs[-1] <= a:
        colors_maxs.append(a)
    else:
        ind = bisect.bisect_right(colors_maxs, a) # -> 4
        colors_maxs[ind] = a

print(len(colors_maxs))

Submission status: Accepted

Solution code:
from sys import stdin
from bisect import bisect

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

dp = []
for a in A[::-1]:
    i = bisect(dp, a)
    if i < len(dp):
        dp[i] = a
    else:
        dp.append(a)
print(len(dp))

Submission status: Accepted

Solution code:
n = int(raw_input())
ais = [int(raw_input()) for _ in range(n)]
tails = []
import bisect
for a in ais:
	if not(tails) or (tails[-1] >= a):
		tails.append(a)
	else:
		# maintain a decreaing tails
		986643321
		lo,hi = 0, len(tails) - 1
		while(lo<hi):
			med= (lo + hi)/2
			if tails[med] < a:
				hi = med
			else:
				lo = med + 1
		tails[lo] = a
print len(tails)

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
n = int(input())
a = [int(input()) for _ in range(n)][::-1]
INF = float("INF")
lst = [INF]*n
ans = 0
for i in range(n):
    l = br(lst,a[i])
    lst[l] = a[i]
    ans = max(l+1,ans)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque
from bisect import bisect_left


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = [int(input()) for _ in range(n)]
    ans = deque()
    for ai in a:
        idx = bisect_left(ans, ai)
        if idx == 0:
            ans.appendleft(ai)
        else:
            ans[idx - 1] = ai

    print(len(ans))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
l=deque([])
for i in range(n):
    a=int(input())
    ind=bisect.bisect_right(l,a-1)
    if ind==0:
        l.appendleft(a)
    else:
        l[ind-1]=a
print(len(l))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid]: hi = mid
  else: lo = mid+1
 return lo
def nibun_left(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if a[mid] < x: lo = mid+1
  else: hi = mid
 return lo
N=int(input())
ans=[1]*N
for i in range(N):
 x=int(input())
 c=nibun_right(ans, -x)
 ans[c]=-x
c=nibun_left(ans, 1)
print(c)

Submission status: Accepted

Solution code:

import bisect
from array import array


def slow_solve(N, As):
    colors = []
    for a in As:
        if not colors:
            colors.append(a)
        else:
            if a <= colors[0]:
                colors.append(a)
            else:
                i = bisect.bisect_left(colors, a)
                colors[i-1] = a
        colors.sort()
        print(colors)
    return len(colors)


def solve(N, As):
    colors = array('I', [])
    for a in As:
        if not colors:
            colors.append(a)
        else:
            if a <= colors[0]:
                colors.insert(0, a)
            else:
                i = bisect.bisect_left(colors, a)
                colors[i - 1] = a
                j = i - 1
                while j + 1 < len(colors) and colors[j] > colors[j + 1]:
                    colors[j], colors[j + 1] = colors[j + 1], colors[j]
                    j += 1
        # print(colors)
    return len(colors)

#
# for _ in range(100):
#     import random
#     N = 10
#     As = [random.randint(1, 10) for _ in range(5)]
#     if slow_solve(N, As) != solve(N, As):
#         print("OUT")
#         print(N)
#         print(As)
#         input()
# print("OK")

if __name__ == "__main__":
    N = int(input())
    As = []
    [As.append(int(input())) for i in range(N)]
    print(solve(N, As))

Submission status: Accepted

Solution code:
import bisect

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

dp = [float("inf")] * (N+1)
dp[0] = -float("inf")
dp[1] = A[0]

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

for i in reversed(range(N+1)):
    if dp[i] < float("inf"):
        print(i)
        break

Submission status: Accepted

Solution code:
from bisect import bisect_left

N=int(input())

dp=[-2]*(N+1)
dp[N]=-1

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

print(N-bisect_left(dp,0)+1)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**10



    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる
        
        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき
            
            self.cnt=0#要素数を持っておくか
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)
                
            self.cnt+=1#追加

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]
                
            self.cnt-=1

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #x未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)

        def print(self):
            print(self.layer1)
            print(self.layer0)
            
        def len(self):
            return self.cnt

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





        

            
    N=I()
    A=[0]*N
    
    for i in range(N):
        A[i]=I()
        
    ssl = SquareSkipList(square=2000)
    ssl.add(-1)#初期値入れとこ
    
    for i in range(N):
        a=A[i]
        m=ssl.search_lower(a)
        if m==-1:
            ssl.add(a)
        else:
            ssl.remove(m)
            ssl.add(a)
            
    print(ssl.len()-1)
    



main()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**10


    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる
        
        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき
            
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #x未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)

        def print(self):
            print(self.layer1)
            print(self.layer0)
            
        def len(self):
            cnt=0
            for l in self.layer0:
                cnt+=len(l)
            cnt+=len(self.layer1)-1
            return cnt

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



        

            
    N=I()
    A=[0]*N
    
    for i in range(N):
        A[i]=I()
        
    ssl = SquareSkipList(square=2000)
    ssl.add(-1)#初期値入れとこ
    
    for i in range(N):
        a=A[i]
        m=ssl.search_lower(a)
        if m==-1:
            ssl.add(a)
        else:
            ssl.remove(m)
            ssl.add(a)
            
    print(ssl.len()-1)
    



main()

Submission status: Accepted

Solution code:
import bisect

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

B = [A[-1]]
del A[-1]
for a in reversed(A):
    if B[-1] <= a:
        B.append(a)
    else:
        B[bisect.bisect_right(B,a)] = a
    # print(B)



print(len(B))

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = deque([A[0]])
    for i in range(1,N):
        index = bisect_left(ans,A[i])
        if index == 0:
            ans.appendleft(A[i])
        else:
            ans[index-1] = A[i]

    print(len(ans))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import bisect
def make_LIS(L):
    LIS=[L[0]]
    for i in range(1,len(L)):
        if L[i]>=LIS[-1]:#広義単調増加なら>=に
            LIS.append(L[i])
        else:
            LIS[bisect.bisect_right(LIS,L[i])]=L[i]#広義単調増加の場合，必ずbisect_right
    return len(LIS)
def main():
    n=int(input())
    A=[int(input())for _ in range(n)]
    print(make_LIS(A[::-1]))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import bisect
def make_LIS(L):
    LIS=[L[0]]
    for i in range(1,len(L)):
        if L[i]>=LIS[-1]:#広義単調増加なら>=に
            LIS.append(L[i])
        else:
            LIS[bisect.bisect_right(LIS,L[i])]=L[i]
    return len(LIS)
def main():
    n=int(input())
    A=[int(input())for _ in range(n)]
    print(make_LIS(A[::-1]))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import bisect
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=[int(readline()) for _ in range(n)]

    li=[]
    for i in range(n):
        if i==0:
            li.append(a[i])
        else:
            l=-1
            r=len(li)
            while l<r-1:
                m=(l+r)//2
                if li[m]>=a[i]:
                    l=m
                else:
                    r=m
            if r==len(li):
                li.append(a[i])
            else:
                li[r]=a[i]

    print(len(li))
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
from collections import deque
N = int(input())
my_max = deque([10 ** 9 + 1])
prev = -1
ans = 0
for _ in range(N):
    a = int(input())
    x = bisect.bisect_left(my_max, a) # a未満
    if x == 0: # どれよりも小さい
        my_max.appendleft(a)
        ans += 1
    else:
        my_max[x - 1] = a # a未満の中で最も大きいものと貪欲に同じ色にする
print(ans)

Submission status: Accepted

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

def LIS(L):
    dp = deque([L[0]])
    length = len(L)
    for i in range(1, length):
        a = L[i]
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a
    return dp

print(len(LIS(As[::-1])))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

import bisect
from collections import deque

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

print(len(lis))

Submission status: Accepted

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

import bisect
from collections import deque

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

print(len(lis))

Submission status: Accepted

Solution code:
import bisect
from collections import deque

n = int(input())
lis = deque()

ans = 0
for i in range(n):
    a = int(input())
    if i == 0:
        lis.append(a)
        continue
    l = bisect.bisect_left(lis,a)
    r = bisect.bisect_right(lis,a)
    if l != r :#同じものがある
        if l > 0:#他の色の最大値が上書きできる
            lis[l-1]=a
        elif r ==  len(lis):#全部の色の最大値とaが同じなら追加
            lis.append(a)
        else:#どこかの中に挿入
            lis.appendleft(a)
    elif l == 0:#最小値追加
        lis.appendleft(a)
    else:#最大値更新
        lis[r-1] = a
print(len(lis))

Submission status: Accepted

Solution code:
N = int(input())
l = [-1 for i in range(N)]
for i in range(N):
  A = int(input())
  ok = N-1
  ng = -1
  while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if l[mid] < A:
      ok = mid
    else:
      ng = mid  
  l[ok] = A
###
for i in range(N):
  if l[i] == -1:
    ans = i
    break
  #出会わなかったパターンを忘れ気味
  if i == N-1:
    ans = N  
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

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

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

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

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

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

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

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

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


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

from collections import deque
from bisect import bisect_left

D = deque([])

for a in A:
    i = bisect_left(D,a)
    if i==0:
        D.appendleft(a)
    else:
        D[i-1] = a

print(len(D))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
from collections import deque
def LIS(a):
    lis = deque()
    lis.append(-1)
    for i in range(len(a)):
        index = bisect.bisect_left(lis,a[i])
        if index == 0:
            lis.appendleft(a[i])
        else:
            lis[index-1] = a[i]
    return len(lis)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
from collections import deque

N = int(input())

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

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
N = int(input())
A = [int(input()) for _ in range(N)]

dp = [float('inf')]*(N+1)
for a in A[::-1]:
  idx = bisect.bisect_right(dp, a)
  dp[idx] = a

ans = 0
for n in dp:
  if n != float('inf'):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = list(int(input()) for _ in range(n))
B = [A[n-1]]

for i in range(n-2,-1,-1):
    if A[i] >= B[-1]:
        B.append(A[i])
    else:
        B[bisect.bisect_right(B,A[i])] = A[i]
print(len(B))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
N=int(input())
ls=[int(input()) for _ in range(N)]
color=[ls[-1]]
ans=1
for i in range(N-1):
  a=ls[-2-i]
  k=bisect.bisect_right(color,a)
  if k==ans:
    color.append(a)
    ans+=1
  else:
    color[k]=a
print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = list()
for i in range(N):
  A.append(int(input()))
L = list()
for j in range(N-1, -1, -1):
  n = A[j]
  if(len(L) == 0):
    L.append(n)
  elif(L[-1] <= n):
    L.append(n)
  else:
    x = bisect.bisect_right(L, n)
    L[x] = n
print(len(L))

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
alis = []
for _ in range(n):
    ima = ii()
    ima *= -1
    alis.append(ima)

from bisect import bisect_left as bl
'''index  =  bl(list,num)'''

imaa = [1]*n
for i in range(n):
    index = bl(imaa,alis[i]+1)
    imaa[index] = alis[i]
index = bl(imaa,1)
print(index)

Submission status: Accepted

Solution code:
from collections import deque

def lower_bound(al, key):
    """
    一般に左側が満たしておらず、右側は満たしている判定基準(境目は一つ)ならlower_boundになる
    (条件を満たすもののうち、最小のインデックスを返す)
    単調にさえなっていれば、左右が逆になっていても検索には使える(ng/okも一緒に逆にする必要がある)
    """
    def isOk(a):
        # alの中でkey以上のアイテムのうち最小のインデックスを返す
        # upper_boundにする時にはa>key
        return a>=key

    ng = -1
    ok = len(al)

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok

n = int(input())
l = deque()

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

    if len(l)==0:
        l.append(a)
        continue

    idx = lower_bound(l,a)
    if idx<1:
        l.appendleft(a)
    else:
        l[idx-1] = a

print(len(l))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input()) for _ in range(n)]
from bisect import bisect
b=[]
for i in a:
    j=bisect(b,-i)
    if len(b)==j:
        b.append(-i)
    else:
        b[j]=-i

print(len(b))

Submission status: Accepted

Solution code:
def LIS(l):
    from bisect import bisect_right
    dp = [l[0]+1]
    for i in range(len(l)):
        if l[i] >= dp[-1]:
            dp.append(l[i])
        else:
            dp[bisect_right(dp, l[i])] = l[i]
    return len(dp)
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())
A = [-int(input()) for _ in range(n)]

B = []
for a in A:
  b = bisect_right(B,a)  
  if len(B) == b:    
    B.append(a)    
  else:
    B[b] = a    
    
print(len(B))

Submission status: Accepted

Solution code:
from bisect import bisect_right
n = int(input())
A = [-int(input()) for _ in range(n)]

B = []
v = 0
for a in A:
  b = bisect_right(B,a)  
  if v == b:    
    B.append(a)
    v+=1    
  else:
    B[b] = a    
    
print(len(B))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from bisect import bisect_right
N = int(input())
li_a = []
for _ in range(N):
    a = int(input())
    li_a.append(a)
INF = 10**15
dp = [INF]* N
for i in range(N-1, -1, -1):
    a = li_a[i]
    k = bisect_right(dp, a)
    dp[k] = a
check = INF-1
print(bisect_right(dp, check))

Submission status: Accepted

Solution code:
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def lis_(a):
    dp = [INF]*len(a)
    for i in a:
        dp[bisect.bisect_left(dp, i+1)] = i
    return bisect.bisect_left(dp, INF)

def resolve():
    N = I()
    A = [I() for _ in range(N)]
    A = A[::-1]

    print(lis_(A))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from random import random
from sys import setrecursionlimit

setrecursionlimit(10 ** 5)


class TreapNode:
    _value = None
    _priority = None
    _count = None
    _left = None
    _right = None

    def __init__(self, value):
        self._value = value
        self._priority = random()
        self._count = 1


def treap_rotate_right(n):
    l = n._left
    n._left = l._right
    l._right = n
    return l


def treap_rotate_left(n):
    r = n._right
    n._right = r._left
    r._left = n
    return r


def treap_insert(n, v):
    if n is None:
        return TreapNode(v)
    if n._value == v:
        n._count += 1
        return n
    if n._value > v:
        n._left = treap_insert(n._left, v)
        if n._priority > n._left._priority:
            n = treap_rotate_right(n)
    else:
        n._right = treap_insert(n._right, v)
        if n._priority > n._right._priority:
            n = treap_rotate_left(n)
    return n


def treap_delete(n, v):
    if n is None:
        return None
    if n._value > v:
        n._left = treap_delete(n._left, v)
        return n
    if n._value < v:
        n._right = treap_delete(n._right, v)
        return n

    # n._value == v
    if n._count > 1:
        n._count -= 1
        return n

    if n._left is None and n._right is None:
        return None

    if n._left is None:
        n = treap_rotate_left(n)
    elif n._right is None:
        n = treap_rotate_right(n)
    else:
        # n._left is not None and n._right is not None
        if n._left._priority < n._right._priority:
            n = treap_rotate_right(n)
        else:
            n = treap_rotate_left(n)
    return treap_delete(n, v)


def treap_size(n):
    if n is None:
        return 0
    return n._count + treap_size(n._left) + treap_size(n._right)


def treap_str(n):
    if n is None:
        return ""
    result = []
    if n._left is not None:
        result.append(treap_str(n._left))
    result.append("%d:%d" % (n._value, n._count))
    if n._right is not None:
        result.append(treap_str(n._right))
    return ' '.join(result)


def treap_search(n, v):
    # v 未満で最大のノードを検索する. v 未満のノードがなければ None を返す
    if n is None:
        return None
    if n._value >= v:
        if n._left is None:
            return None
        return treap_search(n._left, v)
    # n._value < v
    if n._right is None:
        return n
    r = treap_search(n._right, v)
    if r is None:
        return n
    return r


class Treap:
    _root = None

    def insert(self, v):
        self._root = treap_insert(self._root, v)

    def delete(self, v):
        self._root = treap_delete(self._root, v)

    def __len__(self):
        return treap_size(self._root)

    def __str__(self):
        return treap_str(self._root)

    def search(self, v):
        return treap_search(self._root, v)


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

t = Treap()
for a in A:
    n = t.search(a)
    if n is not None:
        t.delete(n._value)
    t.insert(a)
print(len(t))