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
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

from bisect import bisect_left, bisect_right  # 二分探索
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー

def main():
    N = i2n()
    A = ii2nn(N)
    B = [1]
    for a in A:
        t = bisect_right(B, -a)
        if t < len(B):
            B[t] = -a
        else:
            B.append(-a)
    print(len(B))

main()

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
B = []
for a in A:
    k = bisect.bisect(B, -a)
    if k == len(B):
        B.append(-a)
    else:
        B[k] = -a
print(len(B))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def local_input():# {{{
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)
# }}}

def solve():
    n = int(input())
    a = []
    
    col = 1

    for _ in range(n):
        a.append(-int(input()))
    
    if n == 1:
        print(col)
        exit()

    b = [a[0]]
    m = 1

    for i in range(1,n):
        x = bisect_right(b,a[i])
        
        if x == m:
            col += 1
            b.append(a[i])
            m += 1
        else:
            b[x] = a[i]
        
    print(col)

    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
        def dump(*args):
            names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
            print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)
    except:
        def dump(*args):
            pass

    solve()

# vim: set foldmethod=marker:}}}

Submission status: Accepted

Solution code:
N = int(input())

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

ans = [a[0]]

for i in range(1, N):

    if  ans[len(ans) - 1] >= a[i]:
        ans.append(a[i])
    elif ans[0] < a[i]:
        ans[0] = a[i]
    elif ans[len(ans) - 2] >= a[i]:
        ans[len(ans) - 1] = a[i]
    else:
        l = 0
        h = len(ans) - 1
        m = (l + h) // 2
        while True:
            if ans[m] >= a[i]:
                l = m
                m = (l + h) // 2
                continue

            if ans[m - 1] < a[i]:
                h = m
                m = (l + h) // 2
                continue
            break
        ans[m] = a[i]

print(len(ans))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input()) for _ in [0]*n]
temp=[]
cnt=0
import bisect
for i in range(n):
    b=bisect.bisect(temp,-a[i])
    if b==cnt:
        temp.append(-a[i])
        cnt+=1
    else:
        temp[b]=-a[i]
print(len(temp))

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
from collections import deque

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())

ans = 1
tops = deque([A[0]])
tops_cnt = 1
for i in range(1,N):
    # print(tops)
    swap_i = bisect.bisect_left(tops,A[i])
    if swap_i:
        # print("hoge",swap_i-1)
        tops[swap_i-1] = A[i]
    # for max_i in range(tops_cnt):
    #     if tops[max_i] < A[i]:
    #         tops[max_i] = A[i]
    #         break
    else:
        tops.appendleft(A[i])
        ans += 1
        tops_cnt += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
As = []
for i in range(N):
  A = int(input())
  As.append(A)
def find2(s, A):
  import math
  a = 0
  b = len(s)
  while a < b:
    i = (a+b)//2
    if s[i] < A:
      b = i
    else:
      if a == i:
        break
      a = i
  return b

num = 1
c = As[0]
s = [c]
for i in range(1,N):
  A = As[i]
  index = find2(s, A)
  #index = -1
  #for j in range(len(s)):
  #  if s[j] < A:
  #    index = j
  #    break
  #print(s, A, index)
  if index < len(s):
    #print(i, A, "B", index)
    s[index] = A
  else:
    #print(i, A, "C")
    num += 1
    s.append(A)
    c = A
print(num)

Submission status: Accepted

Solution code:
def main():

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    """convenient decorator
    # @functools.lru_cache():
    # to facilitate use of recursive function
        # ex:
        # from functools import lru_cache
        # import sys
        # sys.setrecursionlimit(10**9)
        # @lru_cache(maxsize=None)
        # def fib(n):
        #     if n < 2:
        #         return n
        #     return fib(n-1) + fib(n-2)
        # print(fib(1000))
    """
    
    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    # first create factorial_list
    # fac_list = mod_factorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array, use [[0] * N for _ in range(N)]
    # set inputs
        # open(0).read() is a convenient method:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions used
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    if __name__ != '__main__':
        # for test
        sys.stdin = open('sample.txt')

    # ----------------------------------
    # main

    N = int(r())
    A = [-int(r()) for _ in range(N)]
    B = [INF]
    length = 1
    for a in A:
        tmp = bisect_right(B, a)
        if tmp == length:
            B.append(a)
            length += 1
        else:
            B[tmp] = a
    print(length)
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # for
    for k, v in Dic.items():
    """

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
from collections import deque
N = int(input())
A = [int(input()) for i in [0]*N]


ls = deque([A[0]])
for a in A[1:]:
	ind = bisect.bisect_left(ls,a)
	if ind == 0:
		ls.appendleft(a)
	else:
		ls[ind-1] = a

print(len(ls))

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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


def colorfind(a, colors):
    index = bisect.bisect_left(colors, a)
    return index


color = deque([])
for i in range(n):
    if i == 0:
        color.appendleft(a[i])
    elif color[0] >= a[i]:
        color.appendleft(a[i])
    else:
        colorindex = colorfind(a[i], color)
        color[colorindex - 1] = a[i]

print(len(color))

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = [int(input()) for i in range(N)]
d = defaultdict(lambda: [])
for i,a in enumerate(A):
    d[a].append(i)
B = [None for i in range(N)]
for i,k in enumerate(sorted(d.keys())):
    for j in d[k]:
        B[j] = i

bit = [0] * (N+2)
def bit_add(a,w):
    x = a
    while x <= N+1:
        bit[x] += w
        x += (x & -x)

def bit_sum(a):
    x = a
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret

for a in B:
    a += 2

    s = bit_sum(a)
    bit_add(a,1)
    if s and bit_sum(a-1):
        t = bit_sum(a-1)
        ok = a-1
        ng = 0
        while ok-ng > 1:
            m = (ok+ng)//2
            if bit_sum(m) == t:
                ok = m
            else:
                ng = m
        bit_add(ok,-1)

    # for i in range(N+1):
    #     print(i+1, bit_sum(i+1))

print(bit_sum(N+1))

Submission status: Accepted

Solution code:
import bisect
n=int(input())
x=[int(input())for _ in range(n)]
a=[-x[0]]
l=1
for i in range(1,n):
  b=-x[i]
  if a[-1]>b:
    if a[0]>b:a[0]=b;continue
    a[bisect.bisect_right(a,b)]=b
  else:a.append(b);l+=1
print(l)

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
import sys
input=sys.stdin.readline
#s=input()
#l=list(map(int,input().split()))
N=int(input())
A=[int(input()) for i in range(N)]
s=[A[-1]]
for i in range(N-2,-1,-1):
    k=br(s,A[i])
    if len(s)==k:
        s.append(A[i])
    else:
        s[k]=A[i]
print(len(s))

Submission status: Accepted

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
        i = bisect.bisect_right(L, -a)
        L[i] = -a
        ma = L[-1]
    return len(L)



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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

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

print(len(res))

Submission status: Accepted

Solution code:
import heapq as hq
N = int(input())
peak = []
peak_num = 0

def search(lst, n, length):
	l = 0
	r = length
	while r - l > 1:
		p = (l+r) // 2
		if lst[p] < n:
			r = p
		else:
			l = p
	return l

for i in range(N):
	a = int(input())
	if peak_num == 0:
		peak.append(a)
		peak_num += 1
	elif peak[peak_num-1] >= a:
		peak.append(a)
		peak_num += 1
	else:
		n = search(peak, a, peak_num)
		if peak[n] < a:
			peak[n] = a
		else:
			peak[n+1] = a
print(peak_num)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right, bisect_left

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    col = [1] * N
    col[0] = -A[0]
    for a in A[1:]:
        index = bisect_right(col, -a)
        col[index] = -a
        #print(col, index)
    ans = bisect_right(col, 0)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = [int(input())for _ in range(N)]
li = [-1]
for i in A[::-1]:
    if(li[-1]<i):
        li.append(i)
    else:
        ind = bisect.bisect_right(li,i)
        if(ind>=len(li)):
            li.append(i)
        elif(li[ind]>i):
            li.pop(ind)
            li.insert(ind,i)
        else:
            li.pop(ind+1)
            li.insert(ind+1)
print(len(li)-1)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bs
from collections import deque
N=int(input())
pallet=deque()
cnt=0
for _ in range(N):
    A=int(input())
    place=bs(pallet,A)
    if place==0:
        cnt+=1
        pallet.appendleft(A)
    else:
        pallet[place-1]=A
print(cnt)

Submission status: Accepted

Solution code:
def bin_search(temp, x, start, end):
	# print(temp)
	ind = -1
	while start <= end:
		middle = (start + end)//2
		# print(start, middle, end, x)
		if x > temp[middle]:
			ind = middle
			end = middle-1
		else:
			start = middle+1
	# print(ind)
	if ind == -1:
		temp += [x]
	else:
		temp[ind] = x




n = int(input())
arr = []
for i in range(n):
	arr += [int(input())]

temp = [arr[0]]
arr.pop(0)
for x in arr:
	bin_search(temp, x, 0, len(temp)-1)

print(len(temp))

Submission status: Accepted

Solution code:
import bisect


def main():
  x = [int(input()) for _ in range(int(input()))]
  c = [x[-1]]

  for i in range(len(x) - 2, -1, -1):
    j = bisect.bisect(c, x[i])

    if j == len(c):
      c.append(x[i])
    else:
      c[j] = x[i]

  print(len(c))


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import bisect

N = int(input())
L = []
L.append(-int(input()))
c = 1

for i in range(N - 1):
	A = -int(input())
	x = bisect.bisect_right(L, A)
	if x == c:
		L.append(A)
		c += 1
	else:
		L[x] = A

print(c)