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:
# -*- coding: utf-8 -*-

import math

if __name__ == '__main__':
    N = int(input())
    colors = [
        -1
    ]
    # R = [0 for i in range(N)]
    # M = 0

    for i in range(N):
        # print('i={}'.format(i))
        a = int(input())
        for j in range(len(colors)):
            if a > colors[j]:
                colors[j] = a
                break
        else:
            colors.append(
                a
            )

    print(len(colors))

Submission status: Time Limit Exceeded

Solution code:
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
N = int(input())						# 5

B=[]

from bisect import bisect_right as br
from bisect import insort_right as ir

for i in range(N):
	a = int(input())
	
	r = br(B,a)
	if r==0:
		B = [a] + B
	elif r==len(B):
		if B[-1]==a:
			B.append(a)
		else:
			B[-1]=a
	else:
		B[r-1]=a
		
		

	p("  i, a, B",i,a,B)
#
#
#p("A",A)
p("B",B)

print( len(B) )

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
li = [-1]
c = 1
b = -1
index = -1

for _ in range(N):
    n = int(input())
    index = -1
    while n <= b:
        try:
            index -= 1
            b = li[index]
        except BaseException:
            c += 1
            li.append(n)
            break
    li[index] = b = n

print(c)

Submission status: Time Limit Exceeded

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

count = 0
idx = -1
while(True):
  try:
    idx += b[idx+1:].index(0) + 1
  except:
    break
  else:
    comp = a[idx]
    count += 1
    b[idx] = 1
    for i in range(idx+1, n):
      if not b[i] == 0:
        continue
      if a[i] > comp:
        b[i] = 1
        comp = a[i]
    # print(b)
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:


def myinput_int():
    return list(map(int, input().split()))

N, = myinput_int()

now=[-99]*100000
now_len = 1
for i in range(N):
    temp, = myinput_int()
    for j in range(now_len):
        if now[j]<temp :
            if now[j]==-99:
                now_len+=1
            now[j]=temp
            break
    
print(now_len-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
from collections import deque
import bisect

color = [a.pop(0)]
color_count =0 
for ai in a: 
    index = bisect.bisect_left(color, ai)
    if index > 0:
        color[index -1] = ai
    else:
        color.insert(0,ai)
print(len(color))

Submission status: Time Limit Exceeded

Solution code:
def main():
  n = int(input())
  a = []
  stack = []
  count = 1
  last_num = -1
  for i in range(n):
    a.append(int(input()))
  end = [False] * n
  
  stack.append(a[0])
  index = 0
  for i in range(1,n):
    if stack[index] < a[i]:
      stack[index] = a[i]
      continue
    else:
      while True:
        index -= 1
        if index < 0:
          stack.append(a[i])
          index = len(stack)-1
          count += 1
          break
        if stack[index] < a[i]:
          stack[index] = a[i]
          index = len(stack)-1
          break
        else:
          continue
  
  print(count)

main()

Submission status: Time Limit Exceeded

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

for i in range(1, n):
  min_nums = min(nums)
  nn = int(input())
  
  # すでにあるリストのどの数よりも小さければ、リストに追加する
  if nn <= min_nums:
    nums.append(nn)
  
  # リストのある数よりも大きければ、その要素を上書きする
  else:
    # nnより小さく、差が最小の値を選ぶ
    nums_d = max([num for num in nums if num < nn])
    
    # 置き換える
    nums.remove(nums_d)
    nums.append(nn)
    
print(len(nums))

Submission status: Time Limit Exceeded

Solution code:
import io
import sys


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
4
0
0
0
0
'''


def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()

  l = []
  for i in range(0, n):
    num = IN_I()
    # print(l, num)
    for j in range(0, len(l) + 1):
      if j == len(l):
        l.append(num)
      else:
        if l[j] < num:
          l[j] = num
          break

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Time Limit Exceeded

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

import math

if __name__ == '__main__':
    N = int(input())
    A = []
    for i in range(N):
        A.append(
            int(input())
        )
    colors = [
        10000000000
    ]
    # R = [0 for i in range(N)]
    # M = 0

    for i in range(N-1, -1, -1):
        # print('i={}'.format(i))
        for j in range(len(colors)):
            if A[i] < colors[j]:
                colors[j] = A[i]
                break
        else:
            colors.append(
                A[i]
            )

    print(len(colors))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
Ans=[A[-1]]
for i in reversed(range(n-1)):
  a=A[i]
  if a>=Ans[-1]:
    Ans=Ans+[a]
  else:

    Ans[bisect.bisect_right(Ans,a)]=a

print(len(Ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
import math
mod = 10**9 + 7
def I(): return int(input())
def II(): return map(int, input().split())
def L(): return list(map(int, input().split()))
def TWO(M):
  L=[0]*M
  R=[0]*M
  for i in range(M):
    L[i],R[i] = II()
  return L, R

N = I()
A = [0]*N
for i in range(N):
  A[i] = I()

counter = 0
all_counter = 0
not_used = [i for i in range(N)]
while 1:
  temp = -1
  for i in not_used[:]:
    if temp<A[i]:
      temp = A[i]
      all_counter += 1
      not_used.remove(i)
  counter += 1
  if all_counter==N:
    break
  
print(counter)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

import math

if __name__ == '__main__':
    N = int(input())
    A = []
    for i in range(N):
        A.append(
            [int(input()), -1]
        )
    color = 0
    # R = [0 for i in range(N)]
    # M = 0

    for i in range(N-1, -1, -1):
        # print('i={}'.format(i))
        if A[i][1] != -1:
            continue

        current = A[i][0]
        A[i][1] = color

        for j in range(i - 1, -1, -1):
            if A[j][0] < current and A[j][1] == -1:
                current = A[j][0]
                A[j][1] = color

        color += 1

    print(color)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *

input=sys.stdin.readline

def f(n):
    r = []
    for _ in range(n):
        a = int(input())
        if not r:
            r.append(a)
            continue
        i = bisect_left(r, a)
        if i:
            r[i-1]=a
        else:
            r = [a] + r
    print(len(r))

n = int(input())
f(n)

Submission status: Time Limit Exceeded

Solution code:
# Python3 program to insert 
# an element into sorted list 
import bisect 

def insert(list, n): 
	bisect.insort(list, n) 
	return list



n=int(input())
l=[]
q=[]
w=[]
S=[]
D=[]
for i in range(0,n):
    o=int(input())
    l.append(o)
G=0;
for i in range(0,len(l)-1):
    if l[i] <= l[i+1]:
        G=1;
        break;
if G==0:
    print(len(l))
else:
    for i in range(0,len(l)):
        o=l[i]
        if i==0:
            q.append(o)
        else:
            V=-1;
            G=0;
            I=0;
            J=len(q)-1;
            while(I<=J):
                m=(I+J)//2;
                if q[m] < o:
                    V=m;
                    I=m+1;
                else:
                    if q[m]>=o:
                        J=m-1;
            if V==-1:
                q=insert(q,o);
            else:
                q[V]=o;
    print(len(q))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

a1 = int(input())
B = [[a1]]
for n in range(N-1):
  a2 = int(input())
  if a1 < a2:
    B[-1].append(a2)
  else:
    B.append([a2])
  a1 = a2

C = [B[0]]
for n in range(1, len(B)):
  for m in range(1, len(C)+1):
    if C[-m][-1] < B[n][0]:
      C[-m] += B[n]
      break
  else:
    C.append(B[n])

ans = len(C)
print(ans)

Submission status: Time Limit Exceeded

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

colored = [0]*n
ans = 0

i = n-1
while i+1:
    now = i
    if colored[now]:
        i -= 1
        continue
    colored[now] = 1
    ans += 1

    j = now-1
    while j+1:
        if colored[j] or a[j]>=a[now]:
            j -= 1
            continue
        now = j
        colored[now] = 1
        j -= 1
    i -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n = int(input())
A=[int(input()) for _ in range(n)]
row = []
for a in A:
    if (not row) or a<=row[-1]:
        row.append(a)
    else:
        row[len(row) - bisect_left(row[::-1],a)] = a
print(len(row))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
cnt = 0
m = [0] * n
mn = 0
for i in range(0, n):
    if a[i] <= mn:
        m[cnt] = a[i]
        mn = a[i]
        cnt += 1
        continue
    for j in range(cnt):
        if m[j] < a[i]:
            m[j] = a[i]
            break
    else:
        m[cnt] = a[i]
        mn = a[i]
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def myinput_int():
    return list(map(int, input().split()))

N, = myinput_int()

now=[-99]
now_len = len(now)
for i in range(N):
    temp, = myinput_int()
    for j in range(now_len):
        if now[j]<temp :
            if now[j]==-99:
                now.append(-99)
                now_len+=1
            now[j]=temp
            break
    
print(len(now)-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
ans = 0
total = 0
totalall = 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 == m:
            break

print(ans)

Submission status: Time Limit Exceeded

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

count = 0
idx = -1
while(True):
  try:
    idx += b[idx+1:].index(0) + 1
  except:
    break
  else:
    comp = [a[idx]]
    count += 1
    b[idx] = 1
    for i in range(idx+1, n):
      if not b[i] == 0:
        continue
      all = True
      for c in comp:
        if not a[i] > c:
          all = False
          break
      if all:
        b[i] = 1
        comp.append(a[i])
    # print(b)
print(count)

Submission status: Time Limit Exceeded

Solution code:
# Python3 program to insert 
# an element into sorted list 
import bisect 

def insert(list, n): 
	bisect.insort(list, n) 
	return list



n=int(input())
l=[]
q=[]
w=[]
S=[]
D=[]
for i in range(0,n):
    o=int(input())
    l.append(o)
    if i==0:
        q.append(o)
    else:
        V=-1;
        G=0;
        I=0;
        J=len(q)-1;
        while(I<=J):
            m=(I+J)//2;
            if q[m] < o:
                V=m;
                I=m+1;
            else:
                if q[m]>=o:
                    J=m-1;
        if V==-1:
            q=insert(q,o);
        else:
            q[V]=o;
print(len(q))

Submission status: Time Limit Exceeded

Solution code:
input = raw_input

N = int(input())

next_add_i = 0


#in_pairs = [[i, int(input())] for i in range(N)]
#sort_pairs = sorted(in_pairs, key=lambda x: -x[1])
#
#chikai_indexs = [None for _ in range(N)]
#for i, A in sort_pairs:
#    if i == 0:
#        last_i = i
#    else:
#        if last_i < i:



#for i, A in enumerate(A):
for i in range(N):
    A = int(input())

    if i == 0:    
        curs = [A]
        #sort_curs = [[A, next_add_i]]
        sort_curs = [A]
        #count = 1
        next_add_i += 1
    
    else:
        # find_max
        #print("sort_curs", sort_curs)
        #if sort_curs[-1][0] >= A: # if all
        if sort_curs[-1] >= A: # if all
            sort_curs.append(A)
            #sort_curs.append([A, next_add_i])
            next_add_i += 1

        else:
            #for sort_i, (cur_last_A, add_i) in enumerate(sort_curs):
            for sort_i, cur_last_A in enumerate(sort_curs):
                if cur_last_A < A:
                    #sort_curs[sort_i][0] = A
                    sort_curs[sort_i] = A
                    break

print(next_add_i)

Submission status: Time Limit Exceeded

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

B = [[A[0]]]
for n in range(N-1):
  if A[n] < A[n+1]:
    B[-1].append(A[n+1])
  else:
    B.append([A[n+1]])

C = [B[0]]
for n in range(1, len(B)):
  for m in range(1, len(C)+1):
    if C[-m][-1] < B[n][0]:
      C[-m] += B[n]
      break
  else:
    C.append(B[n])

ans = len(C)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
ans_head=[-1]

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

for i in range(n):
  a=a_list[i]
  if ans_head[0]>=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())
l=[]
q=[]
w=[]
S=[]
D=[]
for i in range(0,n):
    o=int(input())
    l.append(o)
    if i==0:
        q.append(o)
    else:
        q.sort(key=int)
        V=-1;
        G=0;
        I=0;
        J=len(q)-1;
        while(I<=J):
            m=(I+J)//2;
            if q[m] < o:
                V=m;
                I=m+1;
            else:
                if q[m]>=o:
                    J=m-1;
        if V==-1:
            q.append(o)
        else:
            q[V]=o;
print(len(q))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N = int(input())
    q = deque()
    min_ = 10**9 + 1
    max_ = 0
    cnt = 0
    for _ in range(N):
        n = int(input())
        if n <= min_:
            q.appendleft(n)
            min_ = n
            cnt += 1
            continue

        if n > max_:
            _ = q.pop()
            q.append(n)
            max_ = n
            continue

        pos = bisect_left(q, n)
        q[pos-1] = n
        min_ = min(q)

    return cnt


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [int(input()) for i in range(n)]
#print(n,l)

L = 0
for i in range(n):
    cnt = 1
    x = l[i]
    for j in range(i+1,n):
        if l[j] <= x:
            cnt += 1
    if L <= cnt:
        L = cnt
print(L)

Submission status: Time Limit Exceeded

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

import bisect as bi


def solve():
    N = int(input())
    A = []
    heads = []
    for _ in range(N):
        A.append(int(input()))
    a = A.pop()
    bi.insort_left(heads, a)
    while A:
        a = A.pop()
        if a < heads[-1]:
            j = -1
            for i, h in enumerate(heads):
                if h > a:
                    j = i
                    break
            del heads[j]
        bi.insort_left(heads, a)
    return len(heads)
  

def main():
    print(solve())


if __name__ == "__main__":
    main()

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

n = int(input())
ans_head=[-1]
for i in range(n):
  a=int(input())
  if ans_head[0]>=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:
inf = float('inf')

n = int(input())
a = tuple(int(input()) for _ in range(n))

c = [inf]

for aa in a:
    push_to = -1
    target = -1
    for i, cc in enumerate(c):
        if target < cc < aa:
            push_to = i
            target = cc
    if push_to != -1:
        c[push_to] = aa
    else:
        c.append(aa)
    # print(c)
print(len(c) - 1)

Submission status: Time Limit Exceeded

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

num_color = 0
for i in range(n):
    l_v = alist[i]
    l_i = i
    t_color = 1
    for j in range(i+1, n):
        if l_v >= alist[j]:
            t_color += 1
            l_i = j
            l_v = alist[j]
    if num_color < t_color:
        num_color = t_color

print(num_color)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
count = [0 for _ in range(n)]
a = []
for i in range(n):
	v = int(input())
	longest = 0
	for j, a_v in enumerate(a):
		if a_v >= v:
			l = count[j] + 1
			if longest < l:
				longest = l
	count[i] = longest
	a.append(v)

print(max(count)+1)

Submission status: Time Limit Exceeded

Solution code:
"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return self.data[self.size:]

from operator import eq

N = int(input())

A = [int(input()) for _ in range(N)]
B = sorted((v,-i) for i,v in enumerate(A))
B = [-i for v,i in B]
i_j = {j:i for i,j in enumerate(B)}

st = SegmentTree.from_initial_data(min, equality=eq, identity=N, data=B)

visit_cnt = 0
cnt = 0
while visit_cnt < N:
    j = 0
    while True:
        i = st[j:]
        if i == N:
            break
        j = i_j[i]
        visit_cnt += 1
        st[j] = N
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

import bisect as bi


def solve():
    N = int(input())
    A = []
    heads = []
    for _ in range(N):
        A.append(int(input()))
    a = A.pop()
    bi.insort_left(heads, a)
    while A:
        a = A.pop()
        if a < heads[-1]:
            k = -1
            for h in heads:
                if h > a:
                    k = h
                    break
            heads.remove(k)
            bi.insort_left(heads, a)
        else:
            bi.insort_left(heads, a)
    return len(heads)
  

def main():
    print(solve())


if __name__ == "__main__":
    main()

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:
import numpy as np
def myinput_int():
    return list(map(int, input().split()))

N, = myinput_int()

now=[-99]
now_len = len(now)
for i in range(N):
    temp, = myinput_int()
    for j in range(now_len):
        if now[j]<temp :
            if now[j]==-99:
                now.append(-99)
                now_len+=1
            now[j]=temp
            now = sorted(now, reverse=True)
            break
    
print(len(now)-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0]*n
for i in range(n):
    a[i]=int(input())
t = a[0]
ans = 0
count = 0

for i in a:
    if t >= i:
        ans += 1
        t = i
    count = a.count(i)

if ans < count:
    ans = count

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = []
    cnt = 0
    for _ in range(N):
        n = int(input())
        check = True
        for i, a in enumerate(A):
            if n > a:
                A[i] = n
                check = False
                break

        if check:
            A.append(n)
            cnt += 1

    return cnt


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N = int(input())
ans = 1
idx = -1
A = [int(input()) for _ in range(N)]
ans = []
for i in range(N):
    if len(ans) == 0:
        ans.append([A[i]])
    else:
        for j in range(len(ans)):
            if ans[j][-1] < A[i]:
                ans[j].append(A[i])
                break
        else:
            ans.append([A[i]])
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

# インデックスの値が増えるにつれて単調増加になる部分は同じ色で良い
# 値が減った時点で違う色が必要になる

# 値を色1リストに追加していく
# 値が減ったら色2リストに値を追加する
# 次の値からは 既存のリストの最大値と比較して、最も差分が小さいリストに追加していく
# ただし、既存のリストの最大値全てよりも小さな値が出てきたらリストを増やして格納する

# 色nリストの最大値だけを持っておくリストを作る
max_arrays = np.array([nums[0]])
# print(f"max_arrays: {max_arrays}")
# 1番目からスタートする
for i in range(1, N):
    current_num = nums[i]
    # print(f"current_num: {current_num}")
    # 既存リストの最大値と比較して最も近くて増加できるリストを探す
    diff_arrays = max_arrays[(current_num - max_arrays) > 0]
    # print(f"diff_arrays: {diff_arrays.size}")
    if diff_arrays.size != 0:
        # print("置き換えるよ")
        most_near_value = np.max(diff_arrays)
        # print(f"most_near_value: {most_near_value}")
        target_index = np.where(max_arrays == most_near_value)[0][0]
        max_arrays[target_index] = current_num
        # print(f"max_arrays: {max_arrays}")
        continue
    # 0未満の値がなければ新規最大値としてリストに追加して次のループへ
    else:
        # print("appendするよ")
        max_arrays = np.append(max_arrays, current_num)
        # print(f"max_arrays: {max_arrays}")
        continue

print(max_arrays.size)

Submission status: Time Limit Exceeded

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

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

q = [A[0]]
for i in range(1,N):
    if q[0] >= A[i]:
        q.insert(0, A[i])
    else:
        insert_index = bisect_left(q,A[i])
        q[insert_index-1] = A[i]

print(len(q))

Submission status: Time Limit Exceeded

Solution code:
N=list(map(int, input().split()))
N=N[0]
A=[]
previous=-1
color=0
for i in range(N):
    I=int(input())
    if I==previous:
        color+=1
    else:
        A.append(I)
    

while len(A)>0:
    color+=1
    max=-1
    sub=[]
    for i in A:
        if i>max:
            max=i
        else:
            sub.append(i)
    A=sub
    
print(color)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = []

def search(n):
    len_a = len(A)
    if len_a == 0:
        A.append(n)
        return 1
    left = 0
    right = len_a-1
    while left < right:
        mid = (left+right) // 2
        if A[mid] == n:
            break
        elif n < A[mid]:
            right = mid-1
        else:
            left = mid+1

    mid = (left + right) // 2
    if A[mid] >= n:
        while mid >= 0:
            if A[mid] < n:
                A[mid] = n
                return 0
            mid -= 1
        if mid == -1:
            A.insert(0, n)
            return 1
    elif A[mid] < n:
        A[mid] = n
        return 0

ans = 0
for _ in range(N):
    a = int(input())
    ans += search(a)

print(ans)

Submission status: Time Limit Exceeded

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


def delete_left_maxvals(i,  A_sort_index):
    A_sort_index_left = [k for k in A_sort_index if k < i]
    if len(A_sort_index_left) == 0:
        A_sort_index.remove(i)
        return A_sort_index
    
    max_index = A_sort_index_left[0]
    A_sort_index.remove(i)

    A_sort_index = delete_left_maxvals(max_index,  A_sort_index)
    return A_sort_index


def solve(N: int, A: "List[int]"):
    num_colors = 0

    A_sort_index = sorted(range(len(A)), key=lambda k: A[k], reverse=True)
    
    while True:
        max_idx = A_sort_index[0]
        A_sort_index = delete_left_maxvals(max_idx,  A_sort_index)
        
        num_colors += 1
        if len(A_sort_index) == 0:
            break
    print(num_colors)
    return


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def sort(l, a):
    for i in range(len(l)):
        if(l[i] < a):
            return l[:i] + [a] + l[i+1:]
        
right_list = [A[0]]
if(N == 1):
    print(1)
else:
    for i in range(1, N):
        if(A[i] > right_list[-1]):
            if(A[i] > right_list[0]):
                right_list.pop(0)
                right_list = [A[i]] + right_list 
            else:
                right_list = sort(right_list, A[i])
        else:
            right_list.append(A[i])

print(len(right_list))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
b = [0]
b[0] = a[0]
def check(b, a):
    for i in range(len(b)):
        if i == len(b)-1 and b[i] >= a:
            b.append(a)
            break
        if b[i] < a:

            b[i] = a
  
            break
 
        
for j in range(1,n):
    check(b,a[j])

print(len(b))

Submission status: Time Limit Exceeded

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

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

q = [A[0]]
for i in range(1,N):
    insert_index = bisect_left(q,A[i])
    if insert_index == 0:
        q.insert(0, A[i])
    else:
        q[insert_index-1] = A[i]

print(len(q))

Submission status: Time Limit Exceeded

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

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

An=[int(input().strip()) for x in range(N)]
An.reverse()

ans=0
while len(An)>0:
    k=An.pop(0)
    ans+=1
    temp=copy.deepcopy(An)
    counter=0
    for i,c in enumerate(temp):
        if c < k:
            An.pop(i-counter)
            k=c
            counter+=1


print(ans)

Submission status: Time Limit Exceeded

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

c = []
for i in range(N):
    n = int(input())
    index = bisect.bisect_left(c,n)
    if index == 0:
        c.append(n)
    else:
        c[index-1] = n
    c.sort()
    #print(c)

print(len(c))

Submission status: Time Limit Exceeded

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