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:
import bisect

N=int(input())
A=[int(input()) for i in range(N)]
count=0
while A:

    nowN=A[-1]
    A.pop()
    count+=1
    i=len(A)-1
    while i>=0:
        if A[i]<nowN:
            nowN=A[i]
            A.pop(i)
        i-=1


    #print(count,A)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=int(input())
A=[int(input()) for i in range(N)]
lst=[]
nowN=max(A)+1
i=0
while i<N:
    if nowN>=A[i]:
        nowN=A[i]
        lst.append([A[i]])
    else:
        lst2=[n[-1] for n in lst]
        if min(lst2)<A[i]:
            for n in range(len(lst2)):
                if lst2[n]<A[i]:
                    lst[n].append(A[i])
                    break
        else:
            lst.append([A[i]])
    i+=1
print(len(lst))

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
A=[int(input()) for i in range(N)]
lst=[]
nowN=max(A)+1
i=0
while i<N:
    if nowN>=A[i]:
        nowN=A[i]
        lst.append([A[i]])
    else:
        flag=0
        for n in range(len(lst)):
            if lst[n][-1]<A[i]:
                lst[n].append(A[i])
                flag=1
                break
        if not flag:
            lst.append([A[i]])
    i+=1
print(len(lst))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
lst=[]
nowN=max(A)+1
i=0
while i<N:
    if nowN>=A[i]:
        nowN=A[i]
        lst.append([A[i]])
    else:
        lst2=[n[-1] for n in lst]
        flag=0
        for n in range(len(lst2)):
            if lst2[n]<A[i]:
                lst[n].append(A[i])
                flag=1
                break
        if not flag:
            lst.append([A[i]])
    i+=1
print(len(lst))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
count=0
nowN=0
while A:
    #print(A)
    nowN=0
    m=1
    deleteFlag=0
    maxA=max(A)
    while m<len(A):
        #print(A[nowN],A[m])
        if A[m]==maxA and A[nowN]<A[m]:
            #print(A[nowN],A[m],"MAX")
            A.pop(m)
            A.pop(nowN)
            deleteFlag=1
            break
        if A[nowN]<A[m]:
            #print( A[nowN],A[m],"hutuu")
            A.pop(nowN)
            nowN=m-1
            deleteFlag=1
        else:
            m+=1
    count+=1
    if not deleteFlag:A.pop(0)

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue


# sys.stdin = open('input')
# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())



def main():
    n = map(int, raw_input().split())[0]
    da = [int(raw_input()) for i in range(n)]
    # print da
    ans = 0
    while da:
        re = []
        st = -1
        for i in da:
            if i>st:
                st = i
            else:
                re.append(i)
        da = re
        ans += 1
    print ans



main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[int(input()) for i in range(N)]
ls=[]
mi=10**10
for elem in a:
  upd_flg=0
  if elem <= mi:
    ls.append(elem)
    mi=elem
    continue
  for i in range(len(ls)):
    if elem > ls[i]:
      ls[i]=elem
      upd_flg=1
      break
  if upd_flg==0:
    ls.append(elem)
    mi=elem
print(len(ls))

Submission status: Time Limit Exceeded

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

max_col=1
for i in range(N-1):
  col=1
  for j in range(i+1,N):
    if A[i] >= A[j]:
      col+=1
  max_col=max(max_col,col)
  
print(max_col)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
ans = int(0)

N = I()
color = []
a = I()
maxcolor =[]
maxcolor.append(a)
lena = 1
for i in range(N-1):
    a = I()
    minmaxcolor = maxcolor[0]
    if a<=minmaxcolor:
        maxcolor.insert(0,a)
#        maxcolor.append(a)
        lena += 1
    else:
        acandi = bisect.bisect_left(maxcolor, a)
        maxcolor[acandi-1] = a
        """
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        
        for _ in range(aupper+1):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2
        """

#print(maxcolor)
ans = len(maxcolor)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
ans = int(0)

N = I()
color = []
a = I()
maxcolor =[]
maxcolor.append(a)
lena = 1
for i in range(N-1):
    a = I()
    minmaxcolor = min(maxcolor)
    if a<=minmaxcolor:
        maxcolor.insert(0,a)
#        maxcolor.append(a)
        lena += 1
    else:
        acandi = bisect.bisect_left(maxcolor, a)
        maxcolor[acandi-1] = a
        """
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        
        for _ in range(aupper+1):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2
        """

#print(maxcolor)
ans = len(maxcolor)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
inf = float('inf')
ans = int(0)

N = I()
color = []
a = I()
maxcolor =[]
maxcolor.append(a)
lena = 1
for i in range(N-1):
    a = I()
    minmaxcolor = min(maxcolor)
    if a<=minmaxcolor:
        maxcolor.append(a)
        lena += 1
    else:
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        while (True):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2


#print(maxcolor)
ans = len(maxcolor)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N = I()
color = []
a = int(input())
maxcolor =[]
maxcolor.append(a)
lena = 1
for i in range(N-1):
    a = int(input())
    if a<=min(maxcolor):
        maxcolor.append(a)
        lena += 1
    else:
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        while (True):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2


#print(maxcolor)
ans = len(maxcolor)
print(ans)

Submission status: Time Limit Exceeded

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

count = 0
for i in range(N):
  if A:
    count += 1
    num_temp = A[0]
    while num_temp >= 0:
      try:
      	A.remove(num_temp)
      	num_temp -= 1
      except ValueError:
        num_temp-=1
  else:
    break

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
b = [10**9+1]

for i in a[::-1]:
    if max(b) > i:
        tmp = 10**9+1
        for j in [x for x in b if x > i]:
            if tmp > j:
                tmp = j
        b[b.index(tmp)] = i
    else:
        b.append(i)
print(len(b))

Submission status: Time Limit Exceeded

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

arr = [int(input())]
for _ in range(N-1):
    a = int(input())
    x = bisect.bisect_left(arr, a)
    if x == 0:
        bisect.insort_left(arr, a)
    else:
        arr[x-1] = a


print(len(arr))

Submission status: Time Limit Exceeded

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

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

Color = []
for a in A:
  idx = bisect.bisect_left(Color,a)
  if idx == 0:
    Color.insert(0,a)
  else:
    Color[idx-1] = a
  #Color.sort()
  #print(Color)
print(len(Color))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

Color = []
for a in A:
  idx = bisect.bisect_left(Color,a)
  if idx == 0:
    Color.insert(0,a)
  else:
    Color[idx-1] = a
  #Color.sort()
  #print(Color)
print(len(Color))

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
N,*A=map(int,open(0))
L=[A[0]]
for x in A[1:]:
	i=bisect_left(L,x)
	if i==0:L=[x]+L
	else:L[i-1]=x
print(len(L))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N = int(input())
l = []

for i in range(N):
    a = int(input())
    n = bisect_left(l,a)
    if n != 0:
        l[n-1] = a
    else:
        l = [a] + l
print(len(l))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N = int(input())
l = []

for i in range(N):
    a = int(input())
    n = bisect_left(l,a)
    if n != 0:
        l[n-1] = a
    else:
        l = [a] + l
print(len(l))

Submission status: Time Limit Exceeded

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


def bi(a, x):
    i, j = 0, len(a) - 1
    while i != j:
        k = (i + j) // 2+1
        if a[k] < x:
            i = k
        else:
            j = k - 1
    if a[0] >= x:
        i -= 1
    return i


for i in a:
    j = bi(b, i)
    if j == -1:
        b = [i] + b
        c += 1
    else:
        b[j] = i
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_ls = []
for i in range(n):
    a_ls.append(int(input()))
cnt = 0
while len(a_ls) > 0:
    cnt += 1
    L_ls = [a_ls[0]]
    for a in a_ls[1:]:
        if L_ls[-1] < a:
            L_ls.append(a)
    for a in L_ls:
        a_ls.remove(a)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
a_ls = []
for i in range(n):
    a_ls.append(int(input()))
cnt = 0
while len(a_ls) > 0:
    cnt += 1
    L_ls = [a_ls[0]]
    for a in a_ls[1:]:
        if L_ls[-1] < a:
            L_ls.append(a)
        else:
            L_ls[bisect.bisect_left(L_ls, a)] = a
    for a in L_ls:
        a_ls.remove(a)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []

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

index = 0
color = 0
for _ in range(n):
	color += 1
	minimum = a[index]
	b[index] = 1
	for i in range(index+1,n):
		if b[i] == 0 and minimum < a[i]:
			b[i] = 1
			minimum = a[i]
	if 0 not in b:
		break
	index = b.index(0)

print(color)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = []

for _ in range(n):
    integer = int(input())
    arr.append(-integer)

if arr[1:] == arr[:-1]:
    print(n)
else:
    dp = [1] * n
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[j]+1, dp[i])

    print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
count = 0
for i in range(N):
    a.append(int(input()))
while a != []:
    b = a[0]
    c = [0]
    for j in range(len(a)):
        if a[j] > b:
            c.append(j)
            b = a[j]
    c.reverse()
    for k in c:
        del a[k]
    #print(a)
    count += 1
    if a == []:
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)

    def sum(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

    def __str__(self):
        return "BIT: [{}]".format(
            ", ".join(str(self.sum(i + 1) - self.sum(i))
                      for i in range(self.size))
        )

    def bisect(self, i):
        l, r = 0, i
        s = self.sum(r)
        if s == 0:
            return 0
        while r - l > 1:
            m = (r + l) // 2
            if self.sum(m) < s:
                l = m
            else:
                r = m
        return l + 1


N, *A = map(int, open(0).read().split())

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    i = bit.bisect(b - 1)
    if i != 0:
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Submission status: Time Limit Exceeded

Solution code:
import bisect as b
import sys
input=sys.stdin.readline
n=int(input())
ans=1
clist=[int(input())]
for i in range(n-1):
    next=int(input())
    pos=b.bisect_left(clist,next)
    if pos==0:
        clist=[next]+clist
        ans+=1
    else:
        clist[pos-1]=next
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect as b
n=int(input())
ans=1
clist=[int(input())]
for i in range(n-1):
    next=int(input())
    pos=b.bisect_left(clist,next)
    if pos==0:
        clist=[next]+clist
        ans+=1
    else:
        clist[pos-1]=next
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
if len(np.unique(a)) == 1:
    print(len(a))
else:
    for i in a[::-1][1:]:
        if max(c) <= i:
            c.append(i)
        else:
            c[np.where(np.array(c)>i)[0][0]] = i
    print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
if len(np.unique(a)) == 1:
    print(len(a))
else:
    for i in a[::-1][1:]:
        if c[-1] <= i:
            c.append(i)
            c.sort()
        else:
            c[np.where(np.array(c)>i)[0][0]] = i
    print(len(c))

Submission status: Time Limit Exceeded

Solution code:
N = raw_input()
counter = 0
color_array = []
color_array.append(int(raw_input()))
while counter < int(N)-1:
  newNum = int(raw_input())
  checker = 0
  listlength = len(color_array)
  while checker < listlength:
    if newNum > color_array[checker]:
      color_array[checker] = newNum
      break
    checker += 1
  if checker == listlength:
    color_array.append(newNum)
  counter += 1
  
print len(color_array)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
S = [int(input())]
for _ in range(N-1):
    a = int(input())
    ind = bisect.bisect_right(S,a)
    if S[ind-1]==a:
        ind1 = bisect.bisect_left(S,a)
        if ind1>0 and S[ind1-1]<a:
            S[ind1-1]=a
        else:
            bisect.insort_right(S,a)
    elif ind==0:
        bisect.insort_right(S,a)
    else:
        S[ind-1]=a
#     print("a,S = {}{}".format(a,S))
print(len(S))

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq

n = int(input())
a = []
col1=[]
col2=[]

ans=0
for _ in range(n):
    a.append(int(input()))

minimum=0

for i in range(0,n//2+1,1):
    if not col1:
        col1.append(a[i])
        continue
    
    minimum =col1[0]
        
    if a[i]<=minimum:
        col1.append(a[i])
    else:
        for j,cj in enumerate(col1):
            if a[i] >cj:
                col1[j] = a[i]
                col1.sort()
                break

maxum =0
for i in range(n-1,n//2,-1):
    if not col2:
        col2.append(a[i])
        continue
    maxum =col2[-1]
    if a[i]>=maxum:
        col2.append(a[i])
    else:
        for j,cj in enumerate(col2):
            if a[i] <cj:
                col2[j] = a[i]
                col2.sort()
                break
            
minus = [0 for _ in range(len(col2))]
for i in range(len(col1)-1,-1,-1):
    for j in range(len(col2)-1,-1,-1):
        if col1[i]<col2[j] and (not minus[j]):
            minus[j]=1
            break

print(len(col1)+len(col2)-sum(minus))

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq

n = int(input())
a = []
col=[0]
maxum =0
ans=0
for _ in range(n):
    a.append(int(input()))

for i in range(n-1,-1,-1):
    maxum =col[-1]
    if a[i]>=maxum:
        col.append(a[i])
        ans += 1
    else:
        for j,cj in enumerate(col):
            if a[i] <cj:
                col[j] = a[i]
                col.sort()
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [0] * N
for i in range(N):
  A[i] = int(input())
  
dp = [-1] * N
count = 0
dp[count] = A[0]
if N ==1:
  print(1)
  exit()

for i in range(1, N):
#  print( 'i_' + str(i))
#  print('A')
#  print(A)
#  print(dp)
  if A[i] <= dp[count]:
    count += 1
    dp[count] = A[i]
  else:
    for j in range(count+1):
#      print('B')
#      print('count_' + str(count))
#      print('j_' + str(j))
#      print('A[i]_'+ str(A[i]))
#      print('dp[j]_' + str(dp[j]))
      if A[i] > dp[j]:
        dp[j] = A[i]
        break
print(count+1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

arr = [0]*n
arr[0] = int(input())
color= [arr[0]]

for i in range(1, n):
	arr[i] = int(input())
	if arr[i] > color[-1]:
		color[-1] = arr[i]
	else:
		maxx = -1
		for idx, c in enumerate(color):
			if c < arr[i] and c > maxx:
				iidx = idx
				maxx = c
		if maxx != -1:
			color[iidx] = arr[i]
		else:
			color.append(arr[i])
print(len(color))

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort, bisect_left
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [int(input()) for i in range(n)]
    l = []
    insort(l, a[0])
    for i in range(1, n):
        index = bisect_left(l, a[i])
        if l[index-1] < a[i]:
            l[index-1] = a[i]
        else:
            insort(l, a[i])
    print(len(l))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

from bisect import insort, bisect_left
n = int(input())
a = [int(input()) for i in range(n)]
l = []
insort(l, a[0])
for i in range(1, n):
    index = bisect_left(l, a[i])
    if l[index-1] < a[i]:
        l[index-1] = a[i]
    else:
        insort(l, a[i])
print(len(l))

Submission status: Time Limit Exceeded

Solution code:
#54 ABC134E

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

import heapq
i=0
heap=[-a[0]]
res=[]
import bisect
for i in range(1,n):
	t=bisect.bisect_right(heap,-a[i])
	if t==0:
		heapq.heapreplace(heap,-a[i])
	elif t>=len(heap):
		heapq.heappush(heap,-a[i])
	else:
		heap[t]=-a[i]
		heapq.heapify(heap)

	#print(heap,t)
print(len(heap))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

colors = []
min_val = 10 ** 10
for num in nums:
	if num <= min_val:
		colors.insert(0, num)
		min_val = num
	else:
		idx_r = bisect.bisect_right(colors, num - 0.5) - 1
		colors[idx_r] = num
		min_val = max(colors[0], min_val)

print(len(colors))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = [int(input()) for _ in range(n)]
colors = {}
cnum = 0

colors[cnum] = arr[-1]
for a in arr[-2::-1]:
  for c in range(cnum + 1):
    if colors[c] > a:
      colors[c] = a
      break
  else:
    cnum += 1
    colors[cnum] = a

print(cnum+1)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    n,*a=map(int,open(0).read().split())
    b=[[a[0]]]
    for i in a[1:]:
        f=0
        for j in range(len(b[:])):
            if b[j][-1]<i:
                b[j].append(i)
                f=1
                break
        if not f:
            b.append([i])
    print(len(b))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    n,*a=map(int,open(0).read().split())
    b=[[a[0]]]
    for i in a[1:]:
        f=0
        for j in range(len(b.copy())):
            if b[j][-1]<i:
                b[j].append(i)
                f=1
                break
        if not f:
            b.append([i])
    print(len(b))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

count = 0
selected = [False for _ in range(n)]
for i in range(n):
    if not selected[i]:
        selected[i] = True
        count += 1

        m = nums[i]
        for j in range(i + 1, n):
            if not selected[j]:
                num = nums[j]
                if num > m:
                    m = num
                    selected[j] = True
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]

b = [a[0]]
b_min = a[0]
for i in range(1, n):
    if a[i] > b_min:
        x = -1
        for j in range(len(b)):
            if b[j] < a[i]:
                if x == -1 or b[j] > b[x]:
                    x = j

        if x == -1:
            b.append(a[i])
        else:
            b[x] = a[i]
    else:
        b.append(a[i])
        b_min = min(b_min, a[i])

print(len(b))

Submission status: Time Limit Exceeded

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

b = [a[0]]
for i in range(1, n):
    x = -1
    for j in range(len(b)):
        if b[j] < a[i]:
            if x == -1 or b[j] > b[x]:
                x = j

    if x == -1:
        b.append(a[i])
    else:
        b[x] = a[i]

print(len(b))

Submission status: Time Limit Exceeded

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

colors = [-1]*N

for a in A:
    for ind,c in enumerate(colors):
        if c < a:
            colors[ind] = a
            break

print(len([x for x in colors if x > -1]))

Submission status: Time Limit Exceeded

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

colors = [[A[0]]]
bef_a = A[0]
now_ind = 0

for a in A[1:]:
    #for ind,color in enumerate(colors):
    if bef_a < a:
        colors[now_ind].append(a)
    else:
        Flag = 1
        for ind,color in enumerate(colors):
            if max(color) < a:
                colors[ind].append(a)
                now_ind = ind
                Flag = 0
                break
        
        if Flag:
            colors.append([a])
            now_ind = len(colors)-1
    bef_a = a
    
print(len(colors))

Submission status: Time Limit Exceeded

Solution code:
import glob
import numpy as np
import collections


# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\134\\E'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class E(Common):

    def resolve(self):

        seq_len = int(self.input_data())
        seq = np.zeros(seq_len, dtype=np.int)
        for i in range(seq_len):
            seq[i] = int(self.input_data())

        count = 0

        for i in range(seq_len):
            if seq[i] != 1000000001:
                count += 1
                index = i
                while True:
                    part = seq[index + 1::]
                    part = part[part > index]
                    seq[index] = 1000000001
                    if len(part) > 0:
                        index = part.argmin() + index + 1
                    else:
                        break

        print(str(count))

    def rec(self, seq, index):

        part = seq[index+1::]
        part = part[part > index]
        seq[index] = 1000000001
        if len(part) > 0:
            next_index = part.argmin() + index + 1
            self.rec(seq, next_index)
        else:
            return


solver = E(REL_PATH)
solver.exec_resolve()

Submission status: Time Limit Exceeded

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

min_stack = [a[-1]]

for i in range(2,n+1):
    if min_stack[-1] <= a[-i]:
        min_stack.append(a[-i])
    else:
        for j in range(len(min_stack)):
            if min_stack[j] > a[-i]:
                min_stack[j] = a[-i]
                break

print(len(min_stack))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import bisect

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

colors = [10 ** 10]
for i in range(N):
    bi = bisect.bisect_left(colors, A[i])
    bir = bisect.bisect_right(colors, A[i])
    if bir == len(A):
        colors[len(A) - 1] = A[i]
    elif bi == 0:
        bisect.insort_left(colors, A[i])
    else:
        colors[bi - 1] = A[i]

print(len(colors) - 1)

Submission status: Time Limit Exceeded

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

N = int(input())

class SortedList:
    def __init__(self):
        self.data = []
        
    def get(self, index):
        if len(self.data) <= index:
            return None
        return self.data[index]
    
    def insort(self, d):
        bisect.insort_left(self.data, d)
        
    def bisect_left(self, d):
        return bisect.bisect_left(self.data, d)
    
d = SortedList()
d.insort(int(input()))
for _ in range(N - 1):
    v = int(input())
    index = d.bisect_left(v)
    
    if d.get(index) == None:
        if d.data[index - 1] < v:
            d.data[index - 1] = v
        else:
            d.insort(v)
    elif d.data[index] < v:
        d.data[index] = v
    elif d.data[index - 1] < v:
        d.data[index - 1] = v
    else:
        d.insort(v)
        
print(len(d.data))

Submission status: Time Limit Exceeded

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

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

class SortedList:
    def __init__(self):
        self.data = [-1] * N
        
    def get(self, index):
        if len(self.data) <= index:
            return None
        return self.data[index]
    
    def insort(self, d):
        self.data[0] = d
        self.data.sort()
        
    def bisect_left(self, d):
        return bisect.bisect_left(self.data, d)
    
    def update(self, index, d):
        self.data[index] = d
        self.data.sort()
        
d = SortedList()
d.insort(L[0])
for v in L[1:]:
    index = d.bisect_left(v)
    
    if d.get(index) == None:
        if d.get(index - 1) < v:
            d.update(index - 1, v)
        else:
            d.insort(v)
    elif d.get(index) < v:
        d.update(index, v)
    elif d.get(index - 1) < v:
        d.update(index - 1, v)
    else:
        d.insort(v)
        
print(len([v for v in d.data if v != -1]))

Submission status: Time Limit Exceeded

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

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

class SortedList:
    def __init__(self):
        self.data = []
        
    def get(self, index):
        if len(self.data) <= index:
            return None
        return self.data[index]
    
    def insort(self, d):
        bisect.insort_left(self.data, d)
        
    def bisect_left(self, d):
        return bisect.bisect_left(self.data, d)
    
d = SortedList()
d.insort(L[0])
for v in L[1:]:
    index = d.bisect_left(v)
    
    if d.get(index) == None:
        if d.data[index - 1] < v:
            d.data[index - 1] = v
        else:
            d.insort(v)
    elif d.data[index] < v:
        d.data[index] = v
    elif d.data[index - 1] < v:
        d.data[index - 1] = v
    else:
        d.insort(v)
        
print(len(d.data))