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:
#E
import heapq
n = int(input())
a = [int(input()) for _ in range(n)]
b = a[:]
heapq.heapify(b)


cnt = 0

while len(a)>0:
    a_l = a.pop(0)
    for i in range(len(a)-1,-1,-1):
        if a[i] > a_l:
            a_r = a.pop(i)
            break
    for j in range(len(a)-1,-1,-1):
        if a_l < a[j] < a_r:
            a_r = a.pop(j)
            
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [int(readline()) for _ in range(n)]
    cnt = 0
    while len(a):
        cnt += 1
        t_a = []
        mt = -1
        for i in range(len(a)):
            if mt >= a[i]:
                t_a.append(a[i])
            else:
                mt = a[i]
        a = t_a
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

color = []
color.append(int(input()))

for i in range(N-1):
  A = int(input())
  for X in range(len(color)):
    if color[X] < A:
      color[X] = A
      X = 10**6
      break
  
  if X != 10**6:
    color.append(A)

print(len(color))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

color = []
color.append(int(input()))

for i in range(N-1):
  A = int(input())
  X = 0
  while X < len(color):
    if color[X] < A:
      color[X] = A
      X = 10**6
    else:
      X += 1
  
  if X != 10**6:
    color.append(A)

print(len(color))

Submission status: Time Limit Exceeded

Solution code:


import bisect

N = int(input())
A = [int(input()) for i in range(N)]
visited = [0]*N
ans = 0
while sum(visited)<N:
    unvisited = [i for i in range(N) if visited[i]==0]
    L = [A[unvisited[0]]] # L[i]==長さi+1の増加部分列の末尾の値のうち最小のもの
    ID = [unvisited[0]]
    for i in unvisited[1:]:
        a = A[i]
        if a > L[-1]:
            # Lの末尾よりaが大きければ増加部分列を延長できる
            L.append(a)
            ID.append(i)
        else:
            # そうでなければ、「aより小さい最大要素の次」をaにする
            # 該当位置は、二分探索で特定できる
            id = bisect.bisect_left(L, a)
            L[id] = a
            ID[id] = i

    for i in range(len(ID)):
        visited[ID[i]] = 1
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    input = sys.stdin.readline

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

    b = [-1]
    for x in a:
        for i, top in enumerate(b):
            if top < x:
                b[i] = x
                break
        else:
            b.append(x)

    ans = len(b)

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
A = [int(input()) for i in range(n)]
m = 10**9
c = 0
X = []
for a in A:
    i = bisect.bisect_left(X, a)
    if i == 0:
        X.reverse()
        X.append(a)
        X.reverse()
    else:
        X[i-1] = a
print(len(X))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
c = [0] * n
ans = 0
for i in range(n):
    if c[i] != 0:
        continue
    ans += 1
    num = a[i]
    c[i] = ans
    for j in range(i + 1, n):
        if a[j] > num and c[j] == 0:
            num = a[j]
            c[j] = ans
# print(c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
seq= [int(input()) for i in range(n)]

# dp[k]:最適に部分列を繋げた時の集合
dp = [seq[0]]

for i in range(1,len(seq)):
    if seq[i] <= dp[0]:
        dp.insert(0,seq[i])

    else:
        dp[bisect.bisect_left(dp, seq[i])-1] = seq[i]

print(len(dp))

Submission status: Time Limit Exceeded

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

def binsearch(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] >= threshold:
            right = mid
        else:
            left = mid
    return left


last=[]
for val in A:
    temp = binsearch(val, last)
    if temp == -1:
        #last.insert(0, val)
        last = [val] + last
    else:
        last[temp] = val
    #print(last)
print(len(last))

Submission status: Time Limit Exceeded

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

def binsearch(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] >= threshold:
            right = mid
        else:
            left = mid
    return left


last=[]
for val in A:
    temp = binsearch(val, last)
    if temp == -1:
        last.insert(0, val)
    else:
        last[temp] = val
    #print(last)
print(len(last))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

for l in L[1:]:
    r = bisect.bisect_left(Q, l)
    if r == 0:
        Q.insert(0, l)
    else:
        Q[r-1] = l
print(len(Q))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

for l in L[1:]:
    #print("Q=>", Q)
    Q = sorted(Q)
    r = bisect.bisect_left(Q, l)
    if r == 0:
        Q.append(l)
        Q = sorted(Q)
    else:
        Q[r-1] = l
print(len(Q))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())

c = []
for i in range(n):
    a = int(input())
    j = bisect.bisect_left(c, a)
    if j == 0:
        c.insert(0, a)
    else:
        c[j-1] = a
print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a1 = int(input())
a = [a1]
for _ in range(n-1):
  ai = int(input())
  if ai <= a[-1]:
    a.append(ai)
  elif ai > a[0]:
    a = [ai]+a[1:]
  else:
    h = 0
    l = len(a)-1
    while l-h>1:
      m = (l+h)//2
      if ai > a[m]:
        l = m
      else:
        h = m
    a = a[:l]+[ai]+a[l+1:]
print(len(a))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N = int(input())
A = [int(input()) for _ in range(N)]
pos = copy.deepcopy(A)
ans = 0
while len(pos) > 0:
    LIS = deque([])
    for i in range(len(pos)):
        temp = bisect.bisect_left(LIS, pos[i])
        if len(LIS) <= temp:
            LIS.append(pos[i])
        else:
            LIS[temp] = pos[i]
    ans += 1
    pos2 = []
    for i in range(len(pos)):
        if len(LIS) != 0:
            if pos[i] == LIS[0]:
                LIS.popleft()
            else:
                pos2.append(pos[i])
        else:
            pos2.append(pos[i])
    pos = pos2
print(ans)

Submission status: Time Limit Exceeded

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

def insert_search(List,a,l,r):
  if r==l:
    List[l-1]=a
    return List
  m=(l+r)//2
  if List[m]<a:
    return insert_search(List,a,m+1,r)
  else:
    return insert_search(List,a,l,m)
for i in range(N-1):
  a=int(input())
  if a>X[-1]:
    X[-1]=a
  elif X[0]>=a:
    X.insert(0,a)
  else:
    X=insert_search(X,a,0,len(X)-1)
print(len(X))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=[int(input())]
for i in range(N-1):
  a=int(input())
  if a>X[-1]:
    X[-1]=a
  elif X[0]>=a:
    X.insert(0,a)
  else:
    for j,x in enumerate(X):
      if x>=a:
        X[j-1]=a
        break
print(len(X))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=[int(input())]
for i in range(N-1):
  a=int(input())
  if a>max(X):
    X[-1]=a
  elif min(X)>=a:
    X.insert(0,a)
  else:
    for j,x in enumerate(X):
      if x>=a:
        X[j-1]=a
        break
print(len(X))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(input()) for i in range(n)]
col=[a[0]]
num=1
for i in range(1,n):
  if col[num-1]>=a[i]:
    col.append(a[i])
    num+=1
  else:
    c=0
    while(a[i]<=col[c]):
      c+=1
    col[c]=a[i]

print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys

# import bisect
# from collections import Counter, deque

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math


# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    c = [-1] * n
    ans = 1

    for number in a:
        for j in range(ans):
            if c[j] < number:
                c[j] = number
                break
        else:
            c[ans] = number
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [int(input()) for _ in range(n)]
lst_rev = lst[::-1]
visited = [False]*n
cnt = 0
for i in range(n):
    if visited[i]:
        continue
    else:
        visited[i] = True
        cnt += 1
        tmp = lst_rev[i]
        for j in range(i+1, n):
            if not visited[j] and lst_rev[j] < tmp:
                visited[j] = True
                tmp = lst_rev[j]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [int(input()) for _ in range(n)]
lst_rev = lst[::-1]

visited = [False]*n
cnt = 0

for i in range(n):
    if visited[i]:
        continue
    else:
        visited[i] = True
        cnt += 1
        tmp = lst_rev[i]
        for j in range(i+1, n):
            if not visited[j] and lst_rev[j] < tmp:
                visited[j] = True
                tmp = lst_rev[j]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

A = []

for i in range(n):
    a = int(input())
    t = 0
    if i == 0:
        A.append(a)
    else:
        if a > A[-1]:
            A[-1] = a
        else:
            for j in range(len(A)):
                if A[j] < a:
                    A[j] = a
                    t = 1
            if t == 0:
                A.append(a)
print(len(A))

Submission status: Time Limit Exceeded

Solution code:
#
#  |    X| | |
#  |  X X| | |
#  |  X X|X|X|X
# X|  X X|X|X|X
# X|X X X|X|X|X
# 2,1,4,5,3,3,3
# R G G G R B Y | R=2, G=1,4,5, R(2回目!)=3, Y=3 
# reverse
# 3 3 3 5 4 1 2
# 1 2 3 4 4 4 🐓 | d = {1:[3], 2:[3], 3:[3], 4:[5,4,1]} で覚えておけば 1->2の色変えで古いやつを使える の判定で良い???? 
n = int(input())
l = []
for i in range(n):
    l.append(int(input()))
l = l[::-1]
l = [9999999999] + l
d = {0:[l[0]]}
mmmax = -1
current_color = 0
for i in range(1,len(l)):
    new_color = True
    if l[i] < d[current_color][-1]:
        color = current_color
        hoges = d[color]
        hoges.append(l[i])
        d[color] = hoges
        new_color = False
        current_color = color
    elif l[i] > mmmax:
        mmax = l[i]
        for color in range(len(d)):  # [0, 0, ,,,0] => 1e5 * 1e5 なのでTLE
            hoges = d[color]
            if l[i] < hoges[-1]:
                hoges.append(l[i])
                d[color] = hoges
                new_color = False
                current_color = color
                break
    if new_color:
        color = len(d)
        current_color = color
        d[color] = [l[i]]
print(len(d))

Submission status: Time Limit Exceeded

Solution code:
#
#  |    X| | |
#  |  X X| | |
#  |  X X|X|X|X
# X|  X X|X|X|X
# X|X X X|X|X|X
# 2,1,4,5,3,3,3
# R G G G R B Y | R=2, G=1,4,5, R(2回目!)=3, Y=3 
# reverse
# 3 3 3 5 4 1 2
# 1 2 3 4 4 4 🐓 | d = {1:[3], 2:[3], 3:[3], 4:[5,4,1]} で覚えておけば 1->2の色変えで古いやつを使える の判定で良い???? 
n = int(input())
l = []
for i in range(n):
    l.append(int(input()))
l = l[::-1]
l = [9999999999] + l
d = {0:[l[0]]}
mmmax = -1
for i in range(1,len(l)):
    new_color = True
    if l[i] > mmmax:
        mmax = l[i]
        for color in range(len(d)):  # [0, 0, ,,,0] => 1e5 * 1e5 なのでTLE
            hoges = d[color]
            if l[i] < hoges[-1]:
                hoges.append(l[i])
                d[color] = hoges
                new_color = False
                break
    if new_color:
        color = len(d)
        d[color] = [l[i]]
print(len(d))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
L = [int(input())]
ans = 0
for i in range(1,n):
    t = int(input())
    k = bisect.bisect_left(L, t)
    if k == 0:
        L.append(t)
        L.sort()
    else:
        L[k-1] = t
print(len(L))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
L = [int(input())]
ans = 0
for i in range(1,n):
    t = int(input())
    k = bisect.bisect_left(L, t)
    if k == 0:
        L.append(t)
    else:
        L[k-1] = t
    L.sort()
print(len(L))

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import deque

n = int(input())
A = []
count = 0
for _ in range(n):
    a = int(input())
    if len(A) == 0:
        A.append(a)
        count += 1
        continue
    i = bisect.bisect_left(A, a)
    if i == 0:
        dq_A = deque(A)
        dq_A.appendleft(a)
        A = list(dq_A)
        count += 1
    else:
        A[i-1] = a

ans = count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
A = []
count = 0
for _ in range(n):
    a = int(input())
    if len(A) == 0:
        A.append(a)
        count += 1
        continue
    i = bisect.bisect_left(A, a)
    if i == 0:
        A = [a] + A
        count += 1
    else:
        A[i-1] = a

ans = count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
A = []
count = 0
for _ in range(n):
    a = int(input())
    if len(A) == 0:
        A.append(a)
        count += 1
        continue
    i = bisect.bisect_left(A, a)
    if i == 0:
        A.insert(0, a)
        count += 1
    else:
        A[i-1] = a

ans = count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
E - Sequence Decomposing
https://atcoder.jp/contests/abc134/tasks/abc134_e
TLE
"""
import sys
from sys import stdin
input = stdin.readline

import bisect

def solve(N, arr):
    res = [arr[0]]
    for a in arr[1:]:
        i = bisect.bisect_left(res, a)
        if i:
            res[i-1] = a
        else:
            res.append(a)
        res.sort()
    return len(res)


def main(args):
    N = int(input())
    arr = [int(input()) for _ in range(N)]
    # N = 100000
    # arr = [0] * N
    ans = solve(N, arr)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
E - Sequence Decomposing
https://atcoder.jp/contests/abc134/tasks/abc134_e

"""
import sys
from sys import stdin
input = stdin.readline

import bisect

def solve(N, arr):
    res = [arr[0]]
    for a in arr[1:]:
        i = bisect.bisect_left(res, a)
        if i:
            x = res.pop(i-1)
        bisect.insort_left(res, a)
    return len(res)



def main(args):
    N = int(input())
    arr = [int(input()) for _ in range(N)]
    # N = 100000
    # arr = [0] * N
    ans = solve(N, arr)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
E - Sequence Decomposing
https://atcoder.jp/contests/abc134/tasks/abc134_e

"""
import sys


import bisect

def solve(N, arr):
    res = [arr[0]]
    for a in arr[1:]:
        i = bisect.bisect_left(res, a)
        if i:
            x = res.pop(i-1)
        bisect.insort_left(res, a)
    return len(res)


def main(args):
    N = int(input())
    arr = [int(input()) for _ in range(N)]
    ans = solve(N, arr)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc134/tasks/abc134_e
import sys
read = sys.stdin.readline
 
 
def read_a_int():
    return int(read())
 
 
from bisect import bisect_left, bisect_right, insort_left
 
 
class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html
 
 
        ls ... 渡す初期配列
        '''
        self.bst = sorted(ls)# insertを爆速にするためにarray型にします。signed long long 前提です
 
    # def __repr__(self):
    #     return f'BST:{self.bst}'
 
    def __len__(self):
        return len(self.bst)
 
    def __getitem__(self, idx):
        return self.bst[idx]
 
    def size(self):
        return len(self.bst)
 
    def insert(self, x):
        # idx = self.bisect_left(x)
        # self.bst.insert(idx,x)
        insort_left(self.bst, x)
 
    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x
 
    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x
 
    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]
 
    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)
 
    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)
 
    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError
 
    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]
 
    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  # xと同じ大きさも削除したいならbisect_left
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]
 
 
N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    # すべてより小さかったら、新しく追加
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        # bstのなかで、aより小さく且つ一番大きい要素をaに書き換えていく
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a
 
print(len(bst))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc134/tasks/abc134_e
import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right, insort_left

class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = sorted(ls)  # insertをO(1)にするためにlistの代わりにdequeを用います

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        insort_left(self.bst, x)

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  # xと同じ大きさも削除したいならbisect_left
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    # すべてより小さかったら、新しく追加
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        # bstのなかで、aより小さく且つ一番大きい要素をaに書き換えていく
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc134/tasks/abc134_e
import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right, insort_left
from collections import deque


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = sorted(ls)  # insertをO(1)にするためにlistの代わりにdequeを用います

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        idx = self.bisect_left(x)
        self.bst.insert(idx, x)
        # insort_left(self.bst, x)

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  # xと同じ大きさも削除したいならbisect_left
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    # すべてより小さかったら、新しく追加
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        # bstのなかで、aより小さく且つ一番大きい要素をaに書き換えていく
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

colors = 0
a = A
while True:
    colors += 1
    p = [a[0]]
    pp = [0]
    for i in range(1,len(a)):
        if p[-1] < a[i]:
            p.append(a[i])
            pp.append(i)
        else:
            pos = bisect.bisect_left(p,a[i])
            p[pos] = a[i]
            pp[pos] = i

    if len(p) == len(a):
        break
    a = [a[x] for x in range(len(a)) if x not in pp]
print (colors)

Submission status: Time Limit Exceeded

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

    color=[]
    for num in a:
        idx=bisect_left(color,num)
        if idx==0:
            color=[num]+color
        else:
            color[idx-1]=num
    
    print(len(color))    
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
G = []
for i in range(N):
    a = A[i]
    gmax = -1
    for j in range(len(G)):
        if G[j][-1]<a:
            if G[j][-1]>gmax:
                gmax = G[j][-1]
                ind = j
    if gmax>=0:
        G[ind].append(a)
    else:
        G.append([a])
print(len(G))

Submission status: Time Limit Exceeded

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

def solve(N: int, A: "List[int]"):
    stack = [-1]

    for i in range(N):
        for j in range(len(stack)):
            if stack[j] < A[i]:
                stack[j] = A[i]
                break
        else:
            stack.append(A[i])
    
    print(len(stack))
    return

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:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, A: "List[int]"):
    stack = [-1]

    for i in range(N):
        for j in range(len(stack)):
            if stack[j] < A[i]:
                stack[j] = A[i]
                break
        else:
            stack.append(A[i])
    
    print(len(stack))
    return



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:
#!/usr/bin/env python3
import sys
from collections import deque
from bisect import bisect_left

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

    for i in range(N):
        for st in stack:
            index = bisect_left(st,A[i])

            if not st or index == len(st):
                st.append(A[i])
                break
            else:
                continue
        else:
            stack.append([A[i]])
    
    print(len(stack))
    return



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

N=int(input())

line=[-1]*10**5

for _ in range(N):
    A=int(input())
    index=bisect.bisect_left(line,A)
    if index==0:
        line[0]=A
    else:
        line[index-1]=A
    line.sort()
    #print(line)
ans=[]
while line:
    num=line.pop(-1)
    if num==-1:
        break
    else:
        ans.append(num)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=int(input())

line=[]

for _ in range(N):
    A=int(input())
    index=bisect.bisect_left(line,A)
    if index==0:
        line.insert(index,A)
    else:
        line[index-1]=A
        line.sort()
    
    #print(line)

print(len(line))

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=int(input())

line=[]

for _ in range(N):
    A=int(input())
    index=bisect.bisect_left(line,A)
    if index==0:
        line.insert(index,A)
    else:
        line.pop(index-1)
        bisect.insort_right(line,A)
    
    #print(line)

print(len(line))

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    use = deque([10**9+1])
    for _ in range(N):
        num = int(input())
        if min(use) >= num:
            use.appendleft(num)
        else:
            index = bisect.bisect_left(use,num)
            use[index-1] = num
    
    print(len(use)-1)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

def main():
    n = int(input())
    a = []
    for _ in range(n):
        target = int(input())
        target = 10**9 + 1 - target 
        index = bisect.bisect_left(a, target)
        if index < len(a) and a[index] > target:
            a[index] = target
        else:
            a.append(target)
        a.sort()
    print(len(a))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = []
for _ in range(N):
    a = ir()
    i = bisect.bisect_left(A, a)
    if i == 0:
        A.insert(0, a)
    else:
        A[i-1] = a

print(len(A))
# 14