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:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353


#############
# Main Code #
#############

N = getN()
A = getArray(N)

ignore = [1] * N

# これ以上進まなくていいよアラート
imos = copy.deepcopy(A)
for i in range(N - 2, -1, -1):
    imos[i] = max(A[i], imos[i + 1])

ans = 0

def lis(A, sta):
    global ans

    if ignore[sta] == 0:
        return

    L = A[sta]
    ignore[sta] = 0

    for a in range(sta + 1, N):
        # Lの末尾よりaが大きければ増加部分を拡張できる
        if A[a] > L and ignore[a] == 1:
            L = A[a]
            ignore[a] = 0
        # これ以上大きいものが見つからないと
        if L >= imos[a]:
            break
    ans += 1

for i in range(N):
    lis(A, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353


#############
# Main Code #
#############

N = getN()
A = getArray(N)

ignore = [1] * N

# これ以上進まなくていいよアラート
imos = copy.deepcopy(A)
for i in range(N - 2, -1, -1):
    imos[i] = max(A[i], imos[i + 1])

ans = 0

def lis(A, sta):
    global ans

    if ignore[sta] == 0:
        return

    L = A[sta]
    ignore[sta] = 0

    for a in range(sta + 1, N):
        # Lの末尾よりaが大きければ増加部分を拡張できる
        if A[a] > L and ignore[a] == 1:
            L = A[a]
            ignore[a] = 0
        # これ以上大きいものが見つからないと
        if L == imos[i]:
            break
    ans += 1

for i in range(N):
    lis(A, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC134E

import sys
from bisect import bisect_left
input=sys.stdin.readline

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    
    lbds=[A[0]]
    for i in range(1,N):
        if lbds[-1]>=A[i]:
            lbds+=[A[i]]
        else:
            x=len(lbds)-bisect_left(lbds[::-1],A[i])
            lbds[x]=A[i]
            
    print(len(lbds))
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

def main():
  N = int(input())
  ans = 1
  lis_min = [int(input())]
  for i in range(N-1):
    a = int(input())
    index = bisect.bisect_left(lis_min, a)
    if index != 0:
      lis_min[index-1] = a
    else:
      ans += 1
      lis_min.insert(index, a)
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

tmp = [li[0]]

for i in range(1,n):
    if li[i] <= min(li):
        tmp.append(li[i])
    else:
        for cnt, j in enumerate(tmp):
            if li[i] > j:
                tmp[cnt] = li[i]
                break

print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
#最長増加部分列問題 (LIS) 
import bisect

N = int(input())
seq = [0] * N
for i in range(N):
  seq[i] = int(input())

LIS = [seq[0]]
#print(LIS)
for i in range(1, len(seq)):
    if seq[i] <= LIS[0]:
        LIS.insert(0, seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i]) - 1] = seq[i]
    #print(LIS)
#print(LIS)
print(len(LIS))

Submission status: Time Limit Exceeded

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

import bisect
#a=[0,2,3,4,67,8]
#a.sort()
#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

color=[-1]

for aa in a:
    i=bisect.bisect_left(color, aa)
    if i==0:
        color.insert(0,aa)
        #print("insert")
    else:
        color[i-1]=aa
        #print("update")
    #print(color,aa) 
print(len(color))

Submission status: Time Limit Exceeded

Solution code:

import bisect

def main():
    N = int(input())
    l = []

    for i in range(N):
        a = int(input())
        if len(l) == 0 or a <= l[0]:
            l.insert(0,a)
        else:
            ind = bisect.bisect_left(l, a)
            l[ind-1] = a

    print(len(l))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
#a = [int(input()) for _ in range(n)]
c = []
for i in range(n):
    a = int(input())
    if i == 0:
        c.append(a)
    else:
        ind = bisect.bisect_left(c,a)
        if ind > 0:
            c[ind-1] = a
        else:
            c = [a] + c[:]

print(len(c))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
#a = [int(input()) for _ in range(n)]
ans = [-1]
l = 1
for i in range(n):
    a = int(input())
    for j in range(l):
        if ans[j] < a:
            ans[j] = a
            a = -1
            break
    if a != -1:
        ans.append(a)
        l += 1
print(l)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n = int(input())
a_list = []
for i in range(n):
    a = int(input())
    index = bisect_left(a_list, a)
    if index == 0:
        a_list = [a] + a_list
    else:
        a_list[index - 1] = a
print(len(a_list))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
ans=0
for i in range(N):
    a=int(input())
    A.append(a)
cl=[A[-1]]
ans=1
for i in range(N-1)[::-1]:
    a=A[i]
    flag=0
    for j in range(len(cl))[::-1]:
        if cl[j]>a:
            cl[j]=a
            flag=1
            break
    if flag==0:
        cl.append(a)
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
ans=0
for i in range(N):
    a=int(input())
    A.append(a)
cl=[A[-1]]
ans=1
for i in range(N-1)[::-1]:
    a=A[i]
    flag=0
    for j in range(len(cl)):
        if cl[j]>a:
            cl[j]=a
            flag=1
            break
    if flag==0:
        cl.append(a)
        ans+=1
        cl.sort()
print(ans)

Submission status: Time Limit Exceeded

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 not(tails[0] < a):
		tails = [a] + tails 
	else:
		m = -1
		for ii in range(len(tails)):
			if tails[ii] < a: m = max(ii, m)
		if m != -1:
			tails[m] = a

print len(tails)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
ais = [int(raw_input()) for _ in range(n)]
tails = []
import bisect
for a in ais:
	if not(tails):
		tails = [a] + tails 
	else:
		m = -1
		for ii in range(len(tails)):
			if tails[ii] < a: m = max(ii, m)
		if m != -1:
			tails[m] = a
		else:
			tails.append(a)

print len(tails)

Submission status: Time Limit Exceeded

Solution code:

import bisect

def solve(N, As):
    colors = []
    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)



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

Submission status: Time Limit Exceeded

Solution code:
import bisect
def 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()
    return len(colors)

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

Submission status: Time Limit Exceeded

Solution code:

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

count = 0
while len(A):
    a = A[0]
    S = []
    for i in range(1, len(A)):
        if a < A[i]:
            a = A[i]
        else :
            S.append(A[i])
    A = S
    count += 1

print(count)

Submission status: Time Limit Exceeded

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

import bisect

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

print(len(lis))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect

n = int(input())
p = [[int(input())]]
for i in range(n-1):
    now = int(input())
    if now > p[0][-1]:
        p[0].append(now)
    else:
        t = bisect_left(p[0],now)
        k = p[0][t]
        p[0][t] = now
        cou = 1
        while True:
            if cou <= len(p) - 1:
                if k > p[cou][-1]:
                    p[cou].append(k)
                    break
                else:
                    t = bisect_left(p[cou],k)
                    nextk = p[cou][t]
                    p[cou][t] = k
                    k = nextk
                    cou += 1
            elif cou == len(p):
                p.append([k])
                break
print(len(p))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
l = [-1 for i in range(N)]
for i in range(N):
  A = int(input())
  for j in range(N):
    if l[j] < A:
      l[j] = A
      break
###
for i in range(N):
  if l[i] == -1:
    ans = i
    break
  #出会わなかったパターンを忘れ気味
  if i == N-1:
    ans = N  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())

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

Submission status: Time Limit Exceeded

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

import heapq as h

node = [-1]


for num in A:
    k = 1
    for i in range(1, len(node)+1):
        if node[-i] < num:
            k = 0
            node[-i] = num
            break
    if k:
        node.insert(0, num)


print(len(node))

Submission status: Time Limit Exceeded

Solution code:
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]
  for j in range(ans):
    if a<color[j]:
      color[j]=a
      break
  else:
    color.append(a)
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

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
  L.sort()
print(len(L))

Submission status: Time Limit Exceeded

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, colored):
    L = []
    L_idx = []
    ret = []
    for i, e in enumerate(a):
        if not colored[i]:
            idx = bisect.bisect_left(L, e)
            if idx==len(L):
                if len(L)>0:
                    ret.append(L_idx[-1])
                L.append(e)
                L_idx.append(i)
            else:
                idx = max(idx, 0)
                L[idx] = e
                L_idx[idx] = i
    ret.append(L_idx[-1])
    return ret

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

    colored = [False]*N
    ans = 0
    while colored.count(False)>0:
        group = lis(A, colored)
        for i in group:
            colored[i] = True
        ans += 1

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, *A = map( int, open( 0 ).read().split() )
L = [ A[ 0 ] ]
for a in A[1:]:
  kl = bisect.bisect_left( L, a )
  if ( kl != 0 ) and ( a != L[ kl -1 ] ):
    L[ kl - 1 ] = a
  else:
    L.insert( kl, a )

print( len( L ) )

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, *A = map( int, open( 0 ).read().split() )
L = [ A[ 0 ] ]
for a in A[1:]:
  kr = bisect.bisect_right( L, a )
  kl = bisect.bisect_left( L, a )
  if kr == len( L ) and ( a != L[ kr -1 ] ):
    L[ kr - 1 ] = a
  elif ( kl != 0 ) and ( a != L[ kl -1 ] ):
    L[ kl - 1 ] = a
  else:
    L.insert( kr, a )

print( len( L ) )

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
Minimum = [A[0]]
for i in range(1,N):
    if A[i] <= Minimum[0]:
        Minimum = [A[i]]+Minimum
    elif A[i] > Minimum[len(Minimum)-1]:
        Minimum[len(Minimum)-1] = A[i]
    else:
        for j in range(len(Minimum)):
            if Minimum[j-1] < A[i] and A[i] <= Minimum[j]:
                Minimum[j-1] = A[i]
print(len(Minimum))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
Minimum = [A[0]]
for i in range(1,N):
    if A[i] <= min(Minimum):
        Minimum = [A[i]]+Minimum
    elif A[i] > max(Minimum):
        Minimum[len(Minimum)-1] = A[i]
    else:
        for j in range(len(Minimum)):
            if Minimum[j-1] < A[i] and A[i] <= Minimum[j]:
                Minimum[j-1] = A[i]
print(len(Minimum))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
Minimum = [[A[0]]]
for i in range(1,N):
    Q = Minimum[i-1].copy()
    if A[i] <= min(Q):
        Q = [A[i]]+Q
    elif A[i] > max(Q):
        Q[len(Q)-1] = A[i]
    else:
        for j in range(len(Q)):
            if Q[j-1] < A[i] and A[i] <= Q[j]:
                Q[j-1] = A[i]
    Minimum.append(Q)
print(len(Minimum[N-1]))

Submission status: Time Limit Exceeded

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

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

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

    print(len(B))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc134/tasks/abc134_e

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
A = []

for _ in range(N):
    A.append(INT())

DP = [0] * N
DP[0] = 1
inc_dic = {0: 0}
color = 0
for i in range(1, N):
    if A[i-1] < A[i]:
        DP[i] = DP[i-1]
        inc_dic[color] = i
        continue
    else:
        for j in inc_dic.keys():
            if A[inc_dic[j]] < A[i]:
                DP[i] = DP[i-1]
                inc_dic[j] = i
                color = j
                break
        else:
            DP[i] = DP[i-1] + 1
            color = max(inc_dic.keys()) + 1
            inc_dic[color] = i

print(DP[-1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
a.append(a[n-1]+1)
l=[0]
for i in range(n):
    if a[i]>=a[i+1]:
        l.sort()
        if l[0]<a[i]:
            l[0]=a[i]
        else:
            l.append(a[i])
    else:
        continue
if l[0]==0:
    print(len(l))
else:
    print(len(l)+1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
a.append(a[n-1]+1)
l=[0]
for i in range(n):
    l.sort()
    if a[i]>=a[i+1]:
        if l[0]<a[i]:
            l[0]=a[i]
        else:
            l.append(a[i])
    else:
        continue
if l[0]==0:
    print(len(l))
else:
    print(len(l)+1)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
Ali = [int(input()) for _ in range(N)]
n = N
c = 0

while n > 0:
  dp = [Ali[0]]
  Ali2 = []
  for i in range(1,n):
    a = Ali[i]
    if a > dp[-1]:
      dp.append(a)
    else:
      b = bisect.bisect_left(dp, a)
      Ali2.append(dp[b])
      dp[b] = a
  Ali = Ali2[::1]
  n = len(Ali)
  c += 1
    
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    for i in range(1, N):
        idx = bisect_left(color, A[i])
        if idx == 0:
            color = [A[i]] + color
        else:
            color[idx - 1] = A[i]

    print(len(color))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from collections import deque
def solve(N,A):
    ans = 0
    lis = []
    for i in range(N):
        ind = bisect_left(lis,A[i])
        if ind == 0:
            lis.insert(0,A[i])
        else:
            lis[ind-1] = A[i]
    ans = len(lis)
    return ans
print(solve(N,A))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = []
for i in range(n):
  a = int(input())
  chk.append((i,a))
  
from bisect import bisect_left,insort_left
ans = 1

c = []
for j in chk:
  i,a = j
  if i == 0:
    c.append((a,n-i))
  else:
    ind = bisect_left(c,(a,n-i))
    if ind == 0:
      ans += 1
      insort_left(c,(a,n-i))
    else:
      c[ind-1] = (a,n-i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = set([])
for i in range(n):
  a = int(input())
  chk.add((i,a))
  
from bisect import bisect_left,insort_left
from operator import itemgetter
chk = sorted(list(chk),key=itemgetter(0))
ans = 1

c = []
for j in chk:
  i,a = j
  if i == 0:
    c.append((a,n-i))
  else:
    ind = bisect_left(c,(a,n-i))
    if ind == 0:
      ans += 1
      insort_left(c,(a,n-i))
    else:
      c[ind-1] = (a,n-i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = []
for i in range(n):
  a = int(input())
  chk.append((i,a))
  
from heapq import heapify,heappop,heappush
from bisect import bisect_left,insort_left
heapify(chk)
ans = 1

c = []
for j in range(n):
  i,a = heappop(chk)
  if j == 0:
    c.append((a,n-i))
  else:
    ind = bisect_left(c,(a,n-i))
    if ind == 0:
      ans += 1
      insort_left(c,(a,n-i))
    else:
      c[ind-1] = (a,n-i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = []
for i in range(n):
  a = int(input())
  chk.append((i,a))
  
from heapq import heapify,heappop,heappush
from bisect import bisect_left,insort_left
heapify(chk)
ans = 1

c = []
for j in range(n):
  i,a = heappop(chk)
  if j == 0:
    c.append((a,n-i))
  else:
    ind = bisect_left(c,(a,n-i))
    if ind == 0:
      ans += 1
      insort_left(c,(a,n-i))
    else:
      c[ind-1] = (a,n-i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
nums = [int(input()) for _ in range(N)]
# i<jで、 AiとAjが同じ色で塗られている場合、Ai < Ajが成り立つ.
# その際に、色の最小数をだす。
LIS = [nums[0]]
count = 0
for index, num in enumerate(nums):
    if index == 0:
        continue
    insert_index = bisect.bisect_left(LIS, num)
    if insert_index == 0:
        LIS.insert(insert_index, num)
    else:
        LIS[insert_index - 1] = num
print(len(LIS))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = [int(input()) for _ in range(N)]
# i<jで、 AiとAjが同じ色で塗られている場合、Ai < Ajが成り立つ.
# その際に、色の最小数をだす。
LISES = [[nums[0]]]

for index, num in enumerate(nums):
    if index == 0:
        continue
    for LIS in LISES:
        if LIS[-1] < num:
            LIS.append(num)
            break
    else:
        LISES.append([num])
print(len(LISES))

Submission status: Time Limit Exceeded

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

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

def solve(N: int):
    tokens = iterate_tokens()
    colors_top = []
    for i in range(N):
        new = int(next(tokens))
        if colors_top:
            b = bisect.bisect_left(colors_top, new)
            if b == 0:
                colors_top = [new] + colors_top
            else:
                colors_top[b-1] = new
        else:
            colors_top.append(new)
    print(len(colors_top))
    return


# Generated by 1.1.6 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():
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

print(len(que))
#print(que)

Submission status: Time Limit Exceeded

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

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

print(len(que))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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


colors = []
for i in range(N):
    if i == 0:
        colors.append(A[i])
    else:
        # 上に積める色がないなら新しく追加
        if A[i] <= colors[0]:
            colors = [A[i]] + colors
        # 積む色がある場合
        else:
            idx = bisect.bisect_left(colors, A[i])
            colors[idx-1] = A[i]


print(len(colors))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
ans = 0
now = -1
while A:
  now = -1
  B = []
  cnt = 0
  used = [0 for _ in range(N)]
  for i in range(len(A)):
    a = A[i]
    if now < a:
      now = a
    else:
      B.append(a)
  A = B[:]
  ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
cnt = 1
tmp = A[0]
for i in range(N):
    if A[i] > tmp:
        tmp = A[i]
        cnt += 1
cnt2 = 1
tmp = A[N-1]
for i in range(N):
    if A[N-1-i] > tmp:
        tmp = A[N-1-i]
        cnt += 1
if cnt2 >= cnt:
    A = A[::-1]
ans = 0
while True:
    tmp = -1
    for i in range(N):
        if A[i] > tmp:
            tmp = A[i]
            A[i] = -1
    if tmp == -1:
        break
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
ans = 0
while True:
    tmp = -1
    for i in range(N):
        if A[i] > tmp:
            tmp = A[i]
            A[i] = -1
    if tmp == -1:
        break
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
for i in range(n):
  ai=int(input())
  a.append(ai)
b=[a[n-1]]
ans=1
for i in reversed(range(n-1)):
  if a[i]>=b[-1]:
    b.append(a[i])
    ans=ans+1
  else:
    for j in range(ans):
      if b[j]>a[i]:
        b[j]=a[i]
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
for i in range(n):
  ai=int(input())
  a.append(ai)
b=[a[n-1]]
for i in reversed(range(n-1)):
  if a[i]>=b[-1]:
    b.append(a[i])
  else:
    for j in range(n):
      if b[j]>a[i]:
        b[j]=a[i]
        break
print(len(b))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
for i in range(n):
  ai=int(input())
  a.append(ai)
b=[a[n-1]]
for i in reversed(range(n-1)):
  if a[i]>=b[-1]:
    b.append(a[i])
  else:
    for j in range(len(b)):
      if b[j]>a[i]:
        b[j]=a[i]
        break
print(len(b))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
color = []
bisect.insort_left(color, int(input()))
for _ in range(n-1):
  key = int(input())
  if key <= color[0]:
    bisect.insort_left(color, key)
  else:
    color[bisect.bisect_left(color, key)-1] = key

print(len(color))

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    INF = 10**10
    col = [INF]
    for _ in range(N):
        num = int(input())
        ind = bisect.bisect_left(col,num)
        if ind == 0:
            col = [num]+col
        else:
            col[ind-1] = num
    
    print(len(col)-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

DP=[[A[0]]]
for i in range(1,n):
    num,flag=A[i],1
    for j in range(len(DP)):
        if DP[j][-1]<num:
            DP[j].append(num)
            flag=0
            break
    if flag:DP.append([num])
    DP=sorted(DP, key=lambda x:x[-1], reverse=True)
print(len(DP))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

temp_list = [-1] * n
ans = 0
for a in a_list:
    for i in range(ans):
        if a > temp_list[i]:
            temp_list[i] = a
            break
    else:
        temp_list[ans] = a
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

temp_list = []
ans = 0
for a in a_list:
    for i in range(ans):
        if a > temp_list[i][-1]:
            temp_list[i].append(a)
            break
    else:
        temp_list.append([a])
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input = sys.stdin.readline
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = A[::-1]
INF = int(1e+9 + 10)
lis = [INF]* (N+1)
lis[-1] = -1
for n in range(N):
    i = bisect.bisect(lis[::-1], A[n])    
    lis[N-i] = A[n]
print (bisect.bisect_left(lis[::-1], INF) - 1)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = A[::-1]
INF = int(1e+9 + 10)
lis = [INF]* (N+1)
lis[-1] = -1
for n in range(N):
    i = bisect.bisect(lis[::-1], A[n])    
    lis[N-i] = A[n]
print (bisect.bisect_left(lis[::-1], INF) - 1)

Submission status: Time Limit Exceeded

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

B = []
import bisect
for i, a in enumerate(A):
    if len(B) == 0:
        B.append(a)
    else:
        j = bisect.bisect_left(B, a)
        if j == 0:
            B = [a]+B
        elif j == len(B):
            B[-1] = a
        else:
            B[j-1] = a
print(len(B))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n = int(input())
x = [int(input())]
for _ in range(n-1):
  a = int(input())
  if a <= x[0]:
    x.insert(0, a)
  else:
    index = bisect_left(x, a)-1
    x[index] = a
print(len(x))