Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

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

Sample Input 1

5
2
1
4
5
3

Sample Output 1

2

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

Sample Input 2

4
0
0
0
0

Sample Output 2

4

We have to paint all the integers with distinct colors.



Sample input:
5
2
1
4
5
3


Sample output:
2

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
class PMS:
    #1-indexed
    def __init__(self, A, B, issum = False):
        #Aに初期状態の要素をすべて入れる,Bは値域のリスト
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        if issum:
            self.sumtree = [0] * (self.size + 1)
            Ssum = [0] + list(accumulate([CA[self.X[i]]*self.X[i] for i in range(self.size)]))
            for i in range(1, 1+self.size):
                self.sumtree[i] = Ssum[i] - Ssum[i - (i&-i)]
    
    def compress(self, L):
        #座圧
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        # 1-indexed
        return L2, C
    
    def leng(self):
        #今入っている個数を取得
        return self.count(self.X[-1])
    
    def count(self, v):
        #v(Bの元)以下の個数を取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        #v(Bの元である必要はない)未満の個数を取得
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        #v(Bの元である必要はない)以下の個数を取得
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, v, x):
        #vをx個入れる,負のxで取り出す,iの個数以上取り出すとエラーを出さずにバグる
        i = self.comp[v]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def get(self, i):
        # i番目の値を取得
        if i <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < i:
                s += k
                i -= self.tree[s]
            k //= 2
        return self.X[s]
    
    def gets(self, v):
        #累積和がv以下となる最大のindexを返す
        v1 = v
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.sumtree[s+k] < v:
                s += k
                v -= self.sumtree[s]
            k //= 2
        if s == self.size:
            return self.leng()
        return self.count(self.X[s]) + (v1 - self.countsum(self.X[s]))//self.X[s]
    
    def addsum(self, i, x):
        #sumを扱いたいときにaddの代わりに使う
        self.add(i, x)
        x *= i
        i = self.comp[i]
        while i <= self.size:
            self.sumtree[i] += x
            i += i & -i
    
    def countsum(self, v):
        #v(Bの元)以下のsumを取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.sumtree[i]
            i -= i & -i
        return s
    
    def getsum(self, i):
        #i番目までのsumを取得
        x = self.get(i)
        return self.countsum(x) - x*(self.count(x) - i)


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

P = PMS([], A)
cnt = 0
for a in A[::-1]:
    t = P.count(a)
    if t == cnt:
        cnt += 1
        P.add(a, 1)
    else:
        v = P.get(t+1)
        P.add(v, -1)
        P.add(a, 1)
print(cnt)

Submission status: Accepted

Solution code:
def lengthOfLIS(nums):
    tails = [0] * len(nums)
    size = 0
    for x in nums:
        i, j = 0, size
        while i != j:
            m = (i + j) // 2
            if tails[m] <= x:
                i = m + 1
            else:
                j = m
        tails[i] = x
        size = max(i + 1, size)
    return size
N=int(input())
A=[]
for i in range(N):
    A+=[-int(input())]
print(lengthOfLIS(A))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
from bisect import bisect_right

n = getN()
mx = []
k = 0
for i in range(n):
    num = -(getN())
    ins = bisect_right(mx, num)
    if ins == k:
        mx.append(num)
        k += 1
    else:
        mx[ins] = num
    # print(ins, mx)

print(len(mx))

Submission status: Accepted

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)
    mi = []
    ans = 0
    for i in range(n):
        j = bisect.bisect_right(mi,-a[i])
        if j == len(mi):
            mi.append(-a[i])
        else:
            mi[j] = -a[i]
    print(len(mi))
    return

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

    return

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

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    Q = deque([])
    c = 0
    for a in A:
        if len(Q) == 0:
            c += 1
            Q.append(a)
            continue
        i = bisect.bisect_left(Q, a)
        if i == 0:
            c += 1
            Q.appendleft(a)
        else:
            Q[i-1] = a
    print(c)
        
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect, bisect_left, bisect_right,insort_right
n=int(input())
a=[int(input()) for i in range(n)]
c=[-1]*n
for i in a:
    c[bisect_left(c,i)-1]=i
print(n-bisect_right(c,-1))

Submission status: Accepted

Solution code:
import bisect
from collections import deque

N = int(input())

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

Submission status: Accepted

Solution code:
def bis(h, a):
  l, r = 0, len(h)-1
  while l<r:
    mid = (l+r) // 2
    if h[mid] >= a:
      l = mid + 1
    else:
      r = mid
  return l

def main():
  n = int(input())
  alist = [int(input()) for _ in range(n)]
  ans = 1
  h = [alist[0]]
  for a in alist[1:]:
    if a <= h[-1]:
      h.append(a)
      ans += 1
    else:
      i = bis(h, a)
      h[i] = a
  print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

n = int(input())
arr = deque()

for _ in range(n):
    i = int(input())
    if not arr:
        arr.append(i)
        continue

    if i <= arr[0]:
        arr.appendleft(i)
        continue

    idx = bisect_left(arr, i)
    arr[idx - 1] = i

    while idx < len(arr) and arr[idx - 1] > arr[idx]:
        arr[idx - 1], arr[idx] = arr[idx], arr[idx - 1]
        idx += 1

print(len(arr))

Submission status: Accepted

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

cnt=0
L=[]
for i in range(N):
    n=int(input())
    L.append(n)
#print(L)
Q=[-1,10**10]
Q=deque()
#Q.appendleft(10**10)
#print(Q)
for i in range(N):
    if bisect.bisect_left(Q,L[i])==0:
        Q.appendleft(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))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = inp()
aa = [inp() for _ in range(N)]

tmp = deque([])
first = True

for a in aa:
    if first:
        tmp.append(a)
        first = False
        continue

    if tmp[0] >= a:
        tmp.appendleft(a)
    else:
        ind = bisect.bisect_left(tmp,a)
        tmp[ind-1] = a

    #print(tmp)

print(len(tmp))

Submission status: Accepted

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


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


print(solve())

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
import bisect




def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    now_list = [-1 for i in range(num)]

    for i in range(num):
        ind = bisect.bisect_left(now_list, data[i])
        now_list[ind - 1] = data[i]

    count = 0
    for i in range(num):
        if now_list[i] >= 0 :
            count += 1

    print(count)




if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 頭にappendは遅いため、逆にする
arr = []
l = 0
for a in A:
  a = -a
  idx = bisect_right(arr, a)
  if idx == l:
    arr.append(a)
    l += 1
  else:
    arr[idx] = a

print(l)

Submission status: Accepted

Solution code:
# search smallest i ( s <= i < e ) such that f(i) == True
def bisearch_smallest(f, s, e = None):
	if e == None:
		e = s - 1
		s = 0
	else:
		e -= 1
	
	while s < e:
		m = (s + e) // 2
		if f(m):
			e = m
		else:
			s = m + 1
	
	if s == e and f(s):
		return s
	else:
		return -1

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

cols = [a_list.pop(0)]

for a in a_list:
	index = bisearch_smallest(lambda i: cols[i] < a, len(cols))
	if index == -1:
		cols.append(a)
	else:
		cols[index] = a

print(len(cols))

Submission status: Accepted

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

n = int(input())


colour_list = [-int(input())]
c = len(colour_list)


for i in range(n-1):
    a = -int(input())
    b = bisect.bisect(colour_list,a)
    if b != c:
        colour_list[b] = a
    else:
        colour_list.append(a)
        c += 1

print(c)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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


dp = [float('inf')] * (N+1)
for A in reversed(As):
    i = bisect_right(dp, A)
    dp[i] = A

print(dp.index(float('inf')))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from bisect import bisect_left

n = ni()
a = [ni() for _ in range(n)]
lists = [[] for _ in range(n)]

lasts = [-1] * n

for ai in a:
    idx = bisect_left(lasts, ai)
    lists[idx-1].append(ai)
    lasts[idx-1] = ai

ans = 0
for lasti in lasts[::-1]:
    if lasti != -1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class BITree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def total(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
N=int(input())
A=[int(input())*(10**5)-i for i in range(N)]
#追加削除
#二分検索
B=[0]+sorted(list(set([i for i in A])))
M=len(B)
D=dict()
for i in range(M):
    D[B[i]]=i
#print(B)
S=BITree(M)
def search(X):
    Y=D[X]
    tmp=S.total(Y)
    if tmp!=S.total(Y-1):
        return Y
    left=0
    right=Y-1
    mid=(left+right)//2
    while(left<=right):
        mid=(left+right)//2
        if S.total(mid)<tmp:
            left=mid+1
        else:
            right=mid-1
    return left
for i in range(N):
    #print([S.total(i+1)-S.total(i) for i in range(M)])
    #print([S.total(i) for i in range(M+1)])
    tmp2=search(A[i])
    if tmp2==0:
        S.add(D[A[i]],1)
    else:
        S.add(D[A[i]],1)
        S.add(tmp2,-1)
print(S.total(M))

Submission status: Accepted

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 = deque()
    for a in al:
        pos = bisect.bisect_left(lsbs, a)
        if pos == 0:
            lsbs.appendleft(a)
        else:
            if pos == len(lsbs):
                lsbs[-1] = a
            else:
                lsbs[pos-1] = a
        # print(lsbs)
    print(len(lsbs))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
A_list = [0] * N
for i in range(N):
    A_list[i] = int(input())

res_list = [-1] * N
for i in range(N):
    j = bisect_left(res_list, A_list[i])
    res_list[j - 1] = A_list[i]

res = 0
for i in range(N):
    if res_list[i] >= 0:
        res += 1

print(res)

Submission status: Accepted

Solution code:
from bisect import bisect

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

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