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())
l = 0
ll = []
g = 0
for i in range(n):
    a = int(input())
    if i==0:
        l = a
        ll.append(l)
        continue

    if l<a:
        ll[g] = a
        continue


    for k in range(len(ll)):
        if ll[k] < a:
            ll[k] = a
            g = k
            break
    else:
        ll.append(a)
        g = len(ll)-1
else:
    print(len(ll))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

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

arr = np.array(a)
jun = np.argsort(arr)
jun = deque(jun)

ans = 0
while jun:
    ans += 1
    i = jun.pop()
    for j in range(i):
        if a[j] != a[i]:
            try:
                jun.remove(j)
            except:
                ValueError

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(int(input()) for _ in range(N))

i = 0
cnt = 0
while i < N:
    start = A[i]
    cnt += 1
    j = i+1
    while j < N:
        if start < A[j]:
            start = A[j]
            del A[j]
            N -= 1
            j -= 1
        j += 1
    i += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:


def solve():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color_list = [-1]
    min_A = min(color_list)
    for a in A:
        if min_A < a:
            for i in range(len(color_list)):
                tag = color_list[i]
                if tag < a:
                    color_list[i] = a
                    if tag == min_A:
                        min_A = min(color_list)
                    break
        else:
            color_list.append(a)
            min_A = a
    # print(color_list)
    print(len(color_list))


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []

colorList_maxnum = []
for i in range(N):
    A.append(int(input()))
    tmp_list = [x for x in colorList_maxnum if x < A[i]]
    if tmp_list:
        colorList_maxnum[colorList_maxnum.index(max(tmp_list))] = A[i]
    else:
        colorList_maxnum.append(A[i])

print(len(colorList_maxnum))

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 _pf(s): return print(s, flush=True)

N = _I()
A = [_I() for i in range(N)]

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

def bisect(arr, val, cmp):
    l = -1
    r = len(arr)
    while r - l > 1:
        e = (l + r) >> 1
        if cmp(arr[e], val): l = e
        else: r = e
    return r

res = [] 
for a in A:
    #  print('a res', a, res)
    if len(res) == 0:
        res.append(a)
    else:
        if a <= res[-1]:
            # 小さいので追加
            res.append(a)
        else:
            # 入れ替え
            p = bisect(res, a, lambda x, y: x > y)
            while res[p] == a:
                p+=1
            else:
                res[p] = a

print(len(res))

Submission status: Time Limit Exceeded

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


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

# a[i] >= a[i+1]の数を数える。条件が成立したa[i]の値を保持する
count = 1
color_pattern = [an[0]]
for i in range(N-1):
    if an[i] >= an[i+1]:
        color_pattern.append(an[i])
        color_pattern.sort(reverse=True)
        # color_patternの色の値より小さければそれを流用すればよい。なるべくでかい値で終わってるところに突っ込んだ方がよい
        for i in range(len(color_pattern)):
            if color_pattern[i] < an[i]:
                color_pattern[i] = an[i]
                break
        else:
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

ans_l = [a[0]]

for i in range(1,n):
    for j in range(len(ans_l)):
        if a[i] > ans_l[j]:
            ans_l[j] = a[i]
            #print(i,j)
            break
    else:
        ans_l.append(a[i])
print(len(ans_l))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
c=0
B=[]
dellist=lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]
for i in range(N):
    A.append(int(input()))
while len(A)>0:
    for j in range(len(A)):
        if A[0]<A[j]:
            B.append(j)
    B.append(0)
    A=dellist(A,B)
    c+=1
    B=[]
print(c)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
ans_head=[-1]
for i in range(n):
  a=int(input())
  if min(ans_head)>=a:
    ans_head=[a]+ans_head
  else:
    insert_index = bisect.bisect_left(ans_head,a)
    ans_head[insert_index-1]=a

  #print(ans_head)
print(len(ans_head))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
B = [10e9 + 1] * N

for i in range(N)[::-1]:
  for j in range(N):
    if A[i] < B[j]:
      B[j] = A[i]
      break

print(len([i for i in B if i != 10e9 + 1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

input = sys.stdin.readline


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

    c = collections.deque([a.pop(0)], 10**5)
    ans = 1

    for i in a:
        if c[0] < i:

            for ci in range(len(c)-1, -1, -1):
                if c[ci] < i:
                    c[ci] = i
                    break
            else:
                c[0] = i
        else:
            c.appendleft(i)
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
B = [int(input())]
C = 1
for i in range(N-1):
    a = int(input())
    if a<=B[0]:
        bisect.insort_left(B,a)
        C+=1
    else:
        B[bisect.bisect_left(B,a)-1] = a
print(C)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []

a = int(input())

val = [a]
length = 1

for _ in range(N - 1) :
    a = int(input())
    i = 0

    while i < length :
        if val[i] < a :
            val[i] = a
            break
        i += 1
    else :
        val.append(a)
        length += 1

print(length)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
used = np.zeros(n, dtype=np.int)

count = 0
for i in range(n):
#     print(used)
    if used[i] == 0:
        used[i] = 1
        tmp = a[i]
        count += 1
#         print(a[i])
        for j in range(i+1, n):
#             print(" aa",a[j])
            if tmp < a[j] and used[j] == 0:
#                 print("ok")
                tmp = a[j]
                used[j] = 1

# print(used)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input())
listofmax = [A[0]]
for j in range(1, N):
    if listofmax[0] >= A[j]:
        listofmax.insert(0, A[j])
    else:
        listofmax[bisect.bisect_left(listofmax, A[j]) - 1] = A[j]
print(len(listofmax))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=1
a=int(input())
m=[a]
for i in range(n-1):
  a=int(input())
  p=0
  for j in range(i+1):
    if a>m[j]:
      m=m[:j]+[a]+m[j:]
      p=1
      break
  if p:
    continue
  ans+=1
  m+=[a]
print(ans)

Submission status: Time Limit Exceeded

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


def fill(n, a, colors, start, c):
    v = -1
    for i in range(start, n):
        if colors[i]:
            continue
        if a[i] <= v:
            continue
        colors[i] = c
        v = a[i]


def solv(n, a):
    colors = [0] * n
    c = 1
    for pos in range(n):
        if colors[pos] == 0:
            fill(n, a, colors, pos, c)
            c += 1
    return c-1


if __name__ == '__main__':

    n = int(input())

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

    ans = solv(n, a)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 20 20:53:54 2019

@author: ctiuser
"""

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

ans = [A[0]]

for i in range(1,N):
    l,r = 0, len(ans)-1
    p = (r-l)//2 + 1
    if A[i] <= ans[r]:
        ans.append(A[i])
    elif A[i] > ans[l]:
        ans[l] = A[i]
    else:
        tmp = p
        while r - l > 1:
            if A[i] > ans[p]:
                tmp = p
                r = p
                p = (r-l)//2
            else:
                l = p
                p = (r-l)//2
        ans[tmp] = A[i]
#    print(i,ans)
print(len(ans))

Submission status: Time Limit Exceeded

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

c = 0
colored = [False for _ in range(N)]
Ls = []
for a in A:

    k = -1
    for i, l in enumerate(Ls):
        if l < a and a > k:
            ind = i
            k = a
    if k != -1:
        Ls[ind] = a
    else:
        Ls.append(a)


print(len(Ls))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import bisect

# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 

# color
c = [a[0]]

for i in range(1,n):
#    print(c)
#    print(p)
    if c[0] >= a[i]:
        c.insert(0,a[i])
    else:
        p = bisect.bisect_right(c, a[i]-1)
        c[p-1]=a[i]
#        c.sort()

print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n=INT()
    a = [INT() for _ in range(n)]

    lis=[]
    clr=1
    clr_lis=[]


    for i in range(n-1):
        if lis==[]:
            if a[i+1] <= a[i]:
                lis.append(i)
                clr+=1

        else:
            if a[i+1] <= a[i]:
                #print('i:',i)
                flg=False
                for j,x in enumerate(lis):
                    if a[i+1] > a[x]:
                        lis[j] =i+1
                        flg=True

                if flg==False:
                    clr+=1
                    lis.append(i)
    
    #print(lis)
    print(clr)

if  __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
INPUT = sys.stdin.readline
#入力関数
def SORO_INT(): return int(INPUT())
def MULT_INT_LIST(): return list(map(int, INPUT().split()))
def MULT_INT_MAP(): return map(int, INPUT().split())
def SORO_STRING(): return INPUT()
def MULT_STRING(): return INPUT().split()
 
N = SORO_INT()
A = list([int(input()) for i in range(N)])
for i in range(0,N):
  for j in range(N):
        if A[i]<A[j] and i<j:
            A[j] = 10**9

t = A.count(10**9)
print(N-t)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
m=[-1]

for i in range(N):
    A=int(input())
    if A<=m[0]:
        m.append(A)
        m.sort()
    else:
        for j in range(len(m)-1,-1,-1):
            if m[j]<A:
                m[j]=A
                break

print(len(m))

Submission status: Time Limit Exceeded

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

answer = 0
i = 0
while len(A) > 0:
  over = [j for j in A if j > A[i]] + [A[i]]
  for j in over:
    A.remove(j)
  answer += 1 if len(over) > 0 else 0

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

arr = np.array(a)
jun = np.argsort(arr)
jun = list(jun)

ans = 0
while jun:
    ans += 1
    i = jun.pop()
    for j in range(i):
        if a[j] != a[i]:
            try:
                jun.remove(j)
            except:
                ValueError

print(ans)

Submission status: Time Limit Exceeded

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

res = 1
l = [a[0]]
for i in a[1:]:
    for j in range(len(l)):
        if l[j] < i:
            l[j] = i
            break
    else:
        l = [i] + l
        res += 1

print(res)

Submission status: Time Limit Exceeded

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


def main():
    n = int(input())

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

    l_unique = list(set(a))
    l_unique_sorted = sorted(l_unique)

    colors = 0
    index = 0
    while len(a) != 0:
        if not l_unique_sorted[index] in a:
            index += 1
            continue

        st_point = a.index(l_unique_sorted[index])

        tmp_max = a[st_point]
        remove_list = [tmp_max]
        for i in range(st_point, len(a)):
            if tmp_max < a[i]:
                remove_list.append(a[i])
                tmp_max = a[i]

        for i in remove_list:
            a.remove(i)

        colors += 1
        # まだ残っている場合は継続
        if l_unique_sorted[index] in a:
            continue
        index += 1

    print(colors)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0

rm = []
remain = []
before = A[0]

while True:
    for i in range(1, len(A)):
        if before < A[i]:
            #rm.append(A[i])
            before = A[i]
        else:
            remain.append(A[i])
    ans = ans + 1
    A = remain
    remain = []
    #rm = []
    if len(A) == 0:
        break
    before = A[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

length = N
ans = 0
while A:
    ans += 1
    head = A[0]
    del A[0]
    length -= 1
    i = 0
    while i < length:
        #print(A,head,A[i])
        if head < A[i]:
            head = A[i]
            #print("del",A[i])
            del A[i]
            length -= 1
        else:
            i += 1

print(ans)

Submission status: Time Limit Exceeded

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

dp = [A[0]]
for k in range(1,N):
    if min(dp) >= A[k]:
        dp.insert(0,A[k])

    elif (max(dp) < A[k]):
        dp[len(dp)-1] = A[k]

    else:
        for i in range(len(dp)):
            if (dp[i] < A[k]) and (A[k] <= dp[i+1]):
                dp[i] = A[k]
                break
    

print(len(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)


def resolve():
    N = [int(x) for x in sys.stdin.readline().split()][0]
    a_list = [[int(x) for x in sys.stdin.readline().split()][0]
              for _ in range(N)]

    logger.debug('{} {}'.format(N, a_list))

    min_list = [10**10]
    for a in reversed(a_list):
        max_min = max(min_list)

        if a >= max_min:
            min_list.append(a)
        else:
            min_list.append(a)
            min_list.remove(max_min)

    print(len(min_list))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
2
1
4
5
3"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
0
0
0
0"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """1
0"""
        output = """1"""
        self.assertIO(input, output)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,*A=map(int,open(0).read().split())
color=np.array([-1])
for a in A:
    if a<=color.min():
        color = np.array(list(color)+[a])
    else:
        close_a = color[color<a].max()
        close_a_index = np.where(color==close_a)[0][0]
        color[close_a_index] = a
print(color.size)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
ans_head=[-1]
for i in range(n):
  a=int(input())
  if min(ans_head)>=a:
    ans_head.append(a)
  else:
    insert_index = bisect.bisect_left(ans_head,a)
    ans_head[insert_index-1]=a

  ans_head.sort()
  #print(ans_head)
print(len(ans_head))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = []
for i in range(N):
  s.append(int(input()))
co = 0
while s != []:
  co  += 1
  t = []
  m = len(s)
  k = s[0]
  for i in range(1,m):
      if s[i] <= k:
        t.append(s[i])
      else:
        k = s[i]
  s = t[:]  
print(co)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 _pf(s): return print(s, flush=True)

N = _I()
A = [_I() for i in range(N)]

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

def bisect(arr, val, cmp):
    l = -1
    r = len(arr)
    while r - l > 1:
        e = (l + r) >> 1
        if cmp(arr[e], val): l = e
        else: r = e
    return r

res = [] 
for a in A:
    #  print('a res', a, res)
    if len(res) == 0:
        res.append(a)
    else:
        if a <= res[-1]:
            # 小さいので追加
            res.append(a)
        else:
            # 入れ替え
            p = bisect(res, a, lambda x, y: x > y)
            c = res.count(a)
            #  print('p,c',p,c)
            #  print('res', res)
            res[p+c] = a
print(len(res))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
numofcolor = 1
A = [0] * N
for i in range(N):
    A[i] = int(input())
listofmax = [A[0]]
for j in range(1, N):
    if listofmax[0] >= A[j]:
        numofcolor += 1
        listofmax.insert(0, A[j])
    else:
        listofmax[bisect.bisect_left(listofmax, A[j]) - 1] = A[j]
print(numofcolor)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
ans = 0
while sum(A) != len(A)*(-1):
    m = max(A)
    ans += 1
    compare = -1
    for i,a in enumerate(A):
        if a != -1:
            if a > compare:
                compare = a
                A[i] = -1
        if a == max(A):
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


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

    logger = [A[0]]

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

    print(len(logger))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
B = [A[0]]
C = 1
for a in A[1:]:
    if a<=B[0]:
        B = [a]+B
        C+=1
    else:
        B[bisect.bisect_left(B,a)-1] = a
print(C)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ans = [A[0]]
# print(ans)

c = 1
for a in A[1:]:
    if a <= ans[0]:  # 色を増やすしかない
        ans.insert(0, a)
        c += 1
    else:  # 既存の色のどこかに追加
        idx = bisect.bisect_left(ans, a)
        ans[idx-1] = a
    # print(a, ans)

# print(ans)
print(c)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
ls=[]
for i in range(N):
  x=int(input())
  ls.append(x)
result=[]
result.append([ls[0]])
for i in range(1,N):
  j=1
  while(j<=len(result)):
    if(ls[i]>result[-j][-1]):
      result[-j].append(ls[i])
      break
    j=j+1
  if(j>len(result)):
    result.append([ls[i]])
print(len(result))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

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

    part = [A[0]]
    for a in A[1:]:
        added = False
        for i in range(len(part)):
            if a > part[i]:
                part[i] = a
                added = True
                break
        if not added:
            part.append(a)
    print(len(part))
main()

Submission status: Time Limit Exceeded

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

color = []
color.append(a.pop(0))
clen = 1
for ai in a:
    for i, c in enumerate(color): 
        if ai > c:
            color[i] = ai
            #color = quick_sort(color)
            break
        else:
            if i+1 == clen:
                color.append(ai)
                clen += 1
                break
print(clen)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
seq = []
ans = 0


def subsequence(seq):
    if not seq:
        return seq

    M = [None] * len(seq)
    P = [None] * len(seq)

    L = 1
    M[0] = 0

    for i in range(1, len(seq)):
        lower = 0
        upper = L

        if seq[M[upper - 1]] < seq[i]:
            j = upper

        else:
            while upper - lower > 1:
                mid = (upper + lower) // 2
                if seq[M[mid - 1]] < seq[i]:
                    lower = mid
                else:
                    upper = mid

            j = lower

        P[i] = M[j - 1]

        if j == L or seq[i] < seq[M[j]]:
            M[j] = i
            L = max(L, j + 1)

    result = []
    pos = M[L - 1]
    for _ in range(L):
        result.append(seq[pos])
        pos = P[pos]

    return result[::-1]


while True:
    if not A:
        break
    ans += 1
    seq = subsequence(A)
    for i in seq:
        A.remove(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
mins = []
for i in range(N):
    A = int(input())
    b = bisect.bisect_left(mins, A)
    if b == 0:
        mins.insert(0, A)
    else:
        mins[b-1] = A

print(len(mins))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
List = [int(input()) for i in range(N)]
k = 0
while len(List)>0:
    a = -1
    A = List[:]
    k += 1
    m = 0
    for i in range(len(A)):
        if a < A[i]:
            a = List.pop(m)
        else:
            m += 1
print(k)

Submission status: Time Limit Exceeded

Solution code:
import math



def search2(S):
    harf = int(len(A)/2)
    for i, a in enumerate(A[harf:]):
        if a < S:
            A[i] = S
            return 
    return

def search(S):

    for i, a in enumerate(A):
        if a < S:
            A[i] = S
            return 
    return



def main():
    N = int(input())
    A[0] = int(input())
    m = A[0]
    harf = 0
    for _ in range(N-1):
        S = int(input())
        if S <= m:
            A.append(S)
        if S <= m:
            search2(S)
        else:
            search(S)
        m = A[-1]
        harf = A[int(len(A)/2)]
    print(len(A))

    

if __name__ == "__main__":
    A = [0]
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def sol():
    n=int(input())
    a=[int(input())]
    for _ in [0]*(n-1):
        new=int(input())
        if a[-1]>=new:a.append(new)
        else:
            for j in range(len(a)):
                if a[j]<new:a[j]=new;break
    print(len(a))
sol()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self, number_list):
        self.root = None
        self.ans = 1
        self.leftMin = 0
        self.leftestNode = None
        self.rightMax = 0
        self.rightestNode = None
        for node in number_list:
            self.insert(node)

    def insert(self, data):
        n = self.root #nにルートを代入
        if n == None: #ルートに何も入っていない場合
            self.root = Node(data) #ルートにノードを代入(二分探索木の一番上の部分が出来る)
            return #呼び出し部分に戻る
        else: #ルートノードに既に数値が入ってる場合
            while True: #return等が入るまでずっと実行
                entry = n.data #entryにnが持つデータ(数値)を入れる
                if data <= entry: # 左
                    if n.left is None: #nの左エッジに何も入っていない場合
                        n.left = Node(data) #nの左エッジにdata(代入するデータ)を代入
                        self.leftestNode = n.left
                        self.ans += 1
                        return ##呼び出し部分に戻る
                    if self.leftMin >= data :
                        self.leftMin = data
                        self.leftestNode.left = Node(data)
                        self.ans += 1
                        return
                    n = n.left #nの左に何か入っている場合nにnのleftを代入
                else: #entryとdata(代入するデータ)を比較してentryの方が小さい場合
                    if n.right is None: #nの右エッジに何も入っていない場合
                        n.right = Node(data) #nの右エッジにdata(代入するデータ)を代入
                        self.rightestNode = n.right
                        return #呼び出し部分に戻る
                    if self.rightMax < data :
                        self.rightestNode = Node(data)
                        self.rightMax = data
                    n.data = max(n.data, data)
                    return
    def getAns(self) :
        return self.ans


for _ in range(N) :
    a = int(input())
    A.append(a)

tree = BST(A)

print(tree.getAns())

Submission status: Time Limit Exceeded

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

def bi2(l,x,c,m):
    ok = c
    ng = -1
    while ok - ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return l[:ok] + [x] + l[ok:c] + l[c+1:]

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
import bisect

# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 

# color
c = [a[0]]

for i in range(1,n):
#    print(c)
#    print(p)
    if c[0] >= a[i]:
        c.insert(0,a[i])
    else:
        p = bisect.bisect_right(c, a[i]-1)
        c[p-1]=a[i]
#        c.sort()

print(len(c))

Submission status: Time Limit Exceeded

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

N = int(input())

c = [int(input())]

for ai in range(1, N):
    a = int(input())
    if a <= c[0]:
        c = [a] + c
    else:
        i = bisect.bisect_left(c, a) - 1
        c[i] = a

print(len(c))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 20 20:53:54 2019

@author: ctiuser
"""

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

ans = [A[0]]

for i in range(1,N):
    l,r = 0, len(ans)-1
    p = (r-0)//2 + 1
    if A[i] <= ans[r]:
        ans.append(A[i])
    elif A[i] > ans[l]:
        ans[l] = A[i]
    else:
        tmp = p
        while r - l > 1:
            if A[i] > ans[p]:
                tmp = p
                r = p
                p = (r-l-0)//2 + 0
            else:
                l = p
                p = (r-l-0)//2 + 0
        ans[tmp] = A[i]
        
#    if i == 6:
#        break
    
#    print(i,ans)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = 0
ll = []
for i in range(n):
    a = int(input())
    if i==0:
        l = a
        ll.append(l)
        continue

    for k in range(len(ll)):
        if ll[k] < a:
            ll[k] = a
            break
    else:
        ll.append(a)
else:
    print(len(ll))

Submission status: Time Limit Exceeded

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

import sys

n= int(sys.stdin.readline())
ai= [ int(sys.stdin.readline()) for _ in range(n) ]
m= [ False ] * n
c= 0
for i in range(n):
    if m[i]: continue
    m[i]= True
    c+= 1
    j= i
    for k in range(j+1,n):
        if m[k]: continue
        if ai[j]<ai[k]:
            m[k]= True
            j= k
#
print( c )

Submission status: Time Limit Exceeded

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

num = 0
while A:
    num += 1
    D = [A[0]]
    for i in range(len(A)):
        if A[i] > D[-1]:
            D.append(A[i])
        else:
            D[bisect_left(D, A[i])] = A[i]

    for i in range(len(D)):
        A.remove(D[i])

print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys,re,copy
input = sys.stdin.readline

N=int(input().strip())

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

for _ in range(N-1):
    A=int(input().strip())
    for i,m in enumerate(ans):
        if A>m:
            ans[i]=A
            break
    else:
        ans.append(A)

print(len(ans))

Submission status: Time Limit Exceeded

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

ans = 0

import copy

while True:
    frg = 0
    n = len(a)
    _a = copy.deepcopy(a)
    _max = 10**9+1
    for i in range(n):
        if _a[n-1-i] < _max:
            _max = a.pop(n-1-i)
            frg = 1
    if frg == 1:
        ans += 1
    else:
        break

print(ans)