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: Wrong Answer

Solution code:
import heapq as hp

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

q = []
for i, a in enumerate(A):
    #print(a, q)
    if i==0:
        hp.heappush(q, -a)
        continue
    b = hp.heappop(q)
    if -a >= b:
        hp.heappush(q, -a)
    hp.heappush(q, b)
        
print(len(q))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
A=[0]*N
for i in range(N):
    A[i]=int(input())
count=1
ans=0
for i in range(N-1):
    #print(ans,A[i],A[i+1])
    if A[i] >= A[i+1]:
        count += 1
    else:
        ans=max(ans,count)
        count =1
print(max(ans,count))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[0]*N
for i in range(N):
  A[i]=int(input())
  
ans=0
for i in range(N-1):
  ans += A[i] >= A[i+1]
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
a_ls = []
for i in range(n):
    a_ls.append(-int(input()))
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
print(len(L_ls))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())

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

B = [A[0]]

for j in range(1,N):
    if B[-1] <= A[j]:
        B.append(A[j])
    else:
        B[bisect.bisect_left(B,A[j])] = A[j]
    #print(B)

print(len(B))

Submission status: Wrong Answer

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

dp = [1] * n
def lis(arr):
    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])

lis(a)
print(dp)

Submission status: Wrong Answer

Solution code:
#E問題
import bisect
N = int(input())
A = [int(input()) for i in range(N)]

C = []
for i in range(N):
    if i == 0:
        C.append(A[i])
    else:
        I = bisect.bisect_right(C,A[i])
        if I == 0:
            bisect.insort_right(C,A[i])
        else:
            if C[I-1] == A[i]:
                bisect.insort_right(C,A[i])
            else:
                c = C.pop(I-1)
                c = A[i]
                bisect.insort_right(C,c)
    #print(C)
print(len(C))

Submission status: Wrong Answer

Solution code:
#E問題
import bisect
N = int(input())
A = [int(input()) for i in range(N)]

C = []
for i in range(N):
    if i == 0:
        C.append(A[i])
    else:
        I = bisect.bisect_right(C,A[i])
        if I == 0:
            bisect.insort_right(C,A[i])
        else:
            if C[I-1] == A[i]:
                bisect.insort_right(C,A[i])
            else:
                C[I-1] = A[i]
            
print(len(C))

Submission status: Wrong Answer

Solution code:
#E問題
import heapq
import bisect
N = int(input())
A = [int(input()) for i in range(N)]

C = []
for i in range(N):
    if i == 0:
        heapq.heappush(C,A[0])
    else:
        I = bisect.bisect_right(C,A[i])
        if I == 0:
            heapq.heappush(C,A[i])
        else:
            if C[I-1] == A[i]:
                bisect.insort_right(C,A[i])
            else:
                C[I-1] = A[i]
            
print(len(C))

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect
n = int(input())
q = deque()

for _ in range(n):
    a = int(input())
    if len(q) == 0:
        q.appendleft(a)
    elif a <= q[0]:
        q.appendleft(a)
    else:
        i = bisect.bisect_right(q, a) - 1
        q[i] = a
print(len(q))

Submission status: Wrong Answer

Solution code:
arr = []

for _ in range(int(input())):
    arr.append(int(input()))

colors = []
m = 10**9+1

for num in arr:
    if num <= m:
        colors.append(num)
        m = min(m, num)
    for i in range(len(colors)):
        if num > colors[i]:
            colors[i] = num
            break
            
    #print(f'colors: {colors}')
print(len(colors))

Submission status: Wrong Answer

Solution code:
arr = []

for _ in range(int(input())):
    arr.append(int(input()))

colors = [arr[0]]
f_min = s_min = arr[0]
for num in arr[1:]:
    if num <= f_min:
        colors.append(num)
        s_min = f_min
        f_min = num

print(len(colors))

Submission status: Wrong Answer

Solution code:
import bisect
n=int(input())
h=[]
for i in range(n):
  a=int(input())
  if len(h)==0:
    h.append(-1*a)
  elif (-1)*a>=h[-1]:
    h.append(-1*a)
  else:
    index=bisect.bisect_left(h,-1*a)
    h[index]=a
print(len(h))

Submission status: Wrong Answer

Solution code:
import bisect
def main():

    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))
    B = [A[-1]]
    for i in range(N-2, -1, -1):
        if B[-1] <= A[i]:
            B.append(A[i])
        else:
            j = bisect.bisect_left(B, A[i])
            B[j] = A[i]
    return len(B)

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

Submission status: Wrong Answer

Solution code:
def main():

    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))
    count = 0
    min_v = float('inf')
    for i in range(N):
        if A[i] <= min_v:
            count += 1
            min_v = A[i]
    return count


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10 ** 7)


def solve(N: int, A: "List[int]"):
    max_len = 0
    now_len = 0
    A.append(-1)
    for i in range(N):
        if A[i] >= A[i + 1]:
            now_len += 1
        else:
            max_len = now_len
            now_len = 0
        # print(now_len)
    print(max(max_len, now_len))
    return


# Generated by 1.1.5 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: Wrong Answer

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_left(self, i):
        bit = self.tree

        while i > 0 and bit[i] == 0:
            i -= i & -i

        if i == 0:
            return 0

        if i & 1:
            return i

        l = i - (i & -i) + ((i & -i) >> 1)
        D = bit[i] - bit[l]
        k = (i & (-i)).bit_length() - 2
        while k > 0:
            if D == 0:
                i = l
                l = l - (l & -l) + ((l & -l) >> 1)
                D = bit[i] - bit[l]
            else:
                l += k
                D = D - bit[l]
            k //= 2

        return l + 1 if D > 0 else l



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_left(b - 1)
    if i != 0:
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Submission status: Wrong Answer

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_left(self, i):
        bit = self.tree

        while i > 0 and bit[i] == 0:
            i -= i & -i

        if i == 0:
            return 0

        if i & 1:
            return i

        l = i - (i & -i) + ((i & -i) >> 1)
        D = bit[i] - bit[l]
        k = (i & (-i)).bit_length() - 2
        while k > 0:
            if D == 0:
                D = bit[l]
                l = l - (l & -l) + ((l & -l) >> 1)
            else:
                l += k
            k //= 2

        return l + 1 if D > 0 else l



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_left(b - 1)
    if i != 0:
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Submission status: Wrong Answer

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_left(self, r):
        bit = self.tree

        if r == 0:
            return 0

        l = 1 << (r.bit_length() - 1)
        if r == l:
            l //= 2

        k = l // 2
        while r - l > 0:
            if bit[r] > bit[l]:
                l += max(1, k)
            else:
                r = l
                l //= 2
            k //= 2
        return r


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:
    if b - 1 < 0 or b - 1 > M:
        print(b)
        quit()
    i = bit.bisect_left(b - 1)
    if i != 0:
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Submission status: Wrong Answer

Solution code:
import sys
import bisect

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

def LIS(seq):
	l = [seq[0]]
	for i in range(1,len(seq)):
	    if seq[i] >= l[-1]:
	        l.append(seq[i])
	    else:
	        l[bisect.bisect_left(l, seq[i])] = seq[i]

	return(len(l))

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

main()

Submission status: Wrong Answer

Solution code:
import sys
import bisect

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

def LIS(seq):
	l = [seq[0]]
	for i in range(len(seq)):
	    if seq[i] >= l[-1]:
	        l.append(seq[i])
	    else:
	        l[bisect.bisect_left(l, seq[i])] = seq[i]

	return(len(l))

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

main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

A.reverse()

dp = [A[0]]
for i, a in enumerate(A[1:]):
    if dp[-1] <= a:
        dp.append(a)
    else:
        dp[bisect_left(dp, a)] = a

print(len(dp))

Submission status: Wrong Answer

Solution code:
def se(c, x, h, l):
    if h == l:
        return l
    t = (h+l)//2
    if c[t] < x:
        a = se(c,x,h,t+1)
    elif c[t] == x:
        return t+1
    else:
        a = se(c,x,t,l)
    return a
        
    
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[se(c,i,len(c),0)] = i
    print(len(c))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ans = 0
cnt = 1
for i in range(N - 1):
    if A[i] >= A[i + 1]:
        cnt += 1
        ans = max(ans, cnt)
    else:
        cnt = 1
print(ans)

Submission status: Wrong Answer

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:
        bisect.insort_right(S,a)
    elif ind==0:
        bisect.insort_right(S,a)
    else:
        S[ind-1]=a
print(len(S))

Submission status: Wrong Answer

Solution code:
import heapq as hq

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

for i in range(n-1,-1,-1):
    maxum =a[-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: Wrong Answer

Solution code:
import heapq as hq

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

for i in range(n-1,-1,-1):
    if a[i]>=maxum:
        col.append(a[i])
        maxum =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: Wrong Answer

Solution code:
import heapq as hq

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

for i in range(n-1,-1,-1):
    if a[i]>maxum:
        col.append(a[i])
        maxum =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: Wrong Answer

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):
#      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] and A[i] > dp[j+1]:
        dp[j+1] = A[i]
        continue
      continue
print(count+1)

Submission status: Wrong Answer

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

for i in range(1, N):
  if A[i] <= dp[count]:
    count += 1
    dp[count] = A[i]
  else:
    for j in range(count):
      if A[i] > dp[j]:
        dp[j] = A[i]
        continue

print(count+1)

Submission status: Wrong Answer

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

for i in range(1, N):
  if A[i] <= dp[count]:
    count += 1
    dp[count] = A[i]
  else:
    for j in range(count):
      if A[i] < dp[j]:
        dp[j] = A[i]
        continue

print(count+1)

Submission status: Wrong Answer

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

for i in range(1, N):
  if A[i] <= dp[count]:
    dp[count] = A[i]
    count += 1
  else:
    for j in range(count):
      if A[i] >= dp[j]:
        dp[j] = A[i]
        continue

print(count+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

n = int(input())
a = list(map(int, input().split()))

def LIS(a, n):
	seq = []
	for ele in a:
		pos = bisect(seq, -ele)
		if len(seq) <= pos:
			seq.append(-ele)
		else:
			seq[pos] = -ele
	return len(seq)

print(LIS(a, n))

Submission status: Wrong Answer

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 = [a[0]]
    #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])
            l.append(a[i])
    print(len(l))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

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

colors = []
max_val = -1 * (10 ** 10)
for num in nums:
	if num >= max_val:
		colors.append(num)
		max_val = num
	else:
		idx_r = bisect.bisect_right(colors, num)
		colors[idx_r] = num
		max_val = min(colors[-1], max_val)
	print(num, colors)

print(len(colors))

Submission status: Wrong Answer

Solution code:
import bisect

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

colors = []
for num in nums:
	idx = bisect.bisect_left(colors, num)
	if idx == 0:
		colors.insert(0, num)
	else:
		idx_r = bisect.bisect_right(colors, num) - 1
		colors[idx_r] = num

print(len(colors))

Submission status: Wrong Answer

Solution code:
import bisect

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

colors = []
for num in nums:
	idx = bisect.bisect_left(colors, num)
	if idx == 0:
		colors.insert(num, 0)
	else:
		idx_r = bisect.bisect_right(colors, num) - 1
		colors[idx_r] = num

print(len(colors))

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
arr = [int(input()) for _ in range(n)]
colors = collections.deque([])

cnum = 0
colors.append(arr[-1])
for a in arr[-2::-1]:
  if a < colors[0]:
    colors[0] = a
    continue
  if a == colors[0]:
    cnum += 1
    colors.appendleft(a)
    continue
  if colors[-1] <= a:
    cnum += 1
    colors.append(a)
    continue
  for i, c in enumerate(colors):
    if a < c:
      colors[i] = a
      break

print(cnum+1)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    A = LIN(N)[::-1] #bisect使いたいので
    LIS = [A[0]] #もとの順序の広義単調減少は反転させた配列の広義単調増加
    for a in A[1:]:
        if LIS[-1] <= a:
            LIS.append(a)
        else:
            update_index = bisect_left(LIS,a)
            LIS[update_index] = a
    print(len(LIS))





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline  #文字列入力では注意！

def main():
        #ttps://atcoder.jp/contests/abc134/submissions/6459172
    from bisect import bisect
    import sys
    input = sys.stdin.readline
    n = int(input())
    A = [int(input()) for _ in range(n)]
    dp = [1]
    for a in A:
        a *= -1
        i = bisect(dp,a)   #既存に-aを挿入した時のindex

        if i < len(dp):    #挿入位置が長さより小さい時（要はabsが一番小さくない時
            dp[i] = a     #-aにする
        else:
           dp.append(a)    #右端に-aを普通に追加

        print(len(dp))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a_lst = [None]*n
color = 0

for i in range(n):
    a_lst[i] = int(input())

for i in range(1, n+1):
    if a_lst[-i] == -1:
        break
    else:
        num = a_lst[-i]
        a_lst[-i] = -1
        for j in range(i+1, n+1):
            if num > a_lst[-j] and a_lst[-j] != -1:
                num = a_lst[-j]
                a_lst[-j] = -1
        color += 1

print(color)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_lst = [None]*n
color = 0

for i in range(n):
    a_lst[i] = int(input())

for i in range(1, n+1):
    if a_lst[-i] == -1:
        break
    else:
        num = a_lst[-i]
        a_lst[-i] = -1
        for j in range(i+1, n+1):
            if num > a_lst[-j]:
                num = a_lst[-j]
                a_lst[-j] = -1
        color += 1

print(color)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
N = int(input())
inf = 10 ** 9 + 1
lis = [inf] * (N + 1)
liscount = [0] * (N + 1)
for _ in range(N):
  a = int(input())
  ind = bl(lis, a)
  if a <= lis[ind]:
    lis[ind] = a
    liscount[ind] -= 1
print(-min(liscount))

Submission status: Wrong Answer

Solution code:
N = int(input())

A = []
for _ in range(N):
    a = int(input())
    A.append(a)
nums = A[:]
colors = [float('inf')] * N

from bisect import bisect_left, bisect_right, insort_right
cnt = 0
ans = 0
for n in nums:
    idx = bisect_right(colors, n)
    colors[idx] = n
    if idx+1 > ans:
        ans = idx+1
            
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())

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

from bisect import bisect_left, bisect_right, insort_right
cnt = 0
for n in nums:
    idx = bisect_right(colors, n)
    if idx == 0:
        insort_right(colors, n)
    else:
        if idx == len(colors):
            if colors[idx-1] == n:
                insort_right(colors, n)
            else:
                colors[idx-1] = max(n, colors[idx-1])
        else:
            if colors[idx] == n:
                insort_right(colors, n)
            else:
                colors[idx] = max(n, colors[idx])
            
    #print(colors)
print(len(colors))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

from bisect import bisect_left, bisect_right, insort_right
cnt = 0
for n in nums:
    idx = bisect_right(colors, n)
    if idx == 0:
        insort_right(colors, n)
    else:
        if idx == len(colors):
            if colors[idx-1] == n:
                insort_right(colors, n)
            else:
                colors[idx-1] = max(n, colors[idx-1])
        else:
            if colors[idx] == n:
                insort_right(colors, n)
            else:
                colors[idx] = max(n, colors[idx])
            
    #print(colors)
print(len(colors))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

from bisect import bisect_left, bisect_right, insort_right
cnt = 0
for n in nums:
    idx = bisect_right(colors, n)
    if idx == 0:
        insort_right(colors, n)
    else:
        if idx == len(colors):
            colors[idx-1] = max(n, colors[idx-1])
        else:
            colors[idx] = max(n, colors[idx])
            
    #print(colors)
print(len(colors))

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
cou = 0
num = 0
for i in range(n):
  a = int(input())
  if num >= a:
    cou += 1
    num = a
  else:
    ans = max(cou,ans)
    cou = 0
    num = 10 ** 10
ans = max(cou,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
cou = 0
num = 10 ** 10
for i in range(n):
  a = int(input())
  if num >= a:
    cou += 1
    num = a
  else:
    ans = max(cou,ans)
    cou = 1
    num = 10 ** 10
ans = max(cou,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
cou = 0
num = 10 ** 10
for i in range(n):
  a = int(input())
  if num >= a:
    cou += 1
    num = a
  else:
    ans = max(cou,ans)
    cou = 0
    num = 10 ** 10
ans = max(cou,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
cou = 0
num = 10 ** 10
for i in range(n):
  a = int(input())
  if num > a:
    cou += 1
    num = a
  else:
    ans = max(cou,ans)
    cou = 0
    num = 10 ** 10
ans = max(cou,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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:
        min_stack[bisect_left(min_stack, a[-i])] = a[-i]

print(len(min_stack))

Submission status: Wrong Answer

Solution code:
import sys
import copy
def input():
    return sys.stdin.readline()
n = int(input())
a = [int(input()) for _ in range(n)]
b = 0
ans = 0

for i in reversed(a):
  if i >= b:
    ans += 1
    b = i
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import bisect

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

colors = [10 ** 8]
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: Wrong Answer

Solution code:
from sys import stdin
import bisect

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

colors = [10 ** 8]
for i in range(N):
    bi = bisect.bisect_left(colors, A[i])
    if bisect.bisect_left(colors, A[i]) == 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: Wrong Answer

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))

Submission status: Wrong Answer

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

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

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)
    
    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.data[index - 1] < v:
            d.update(index - 1, v)
        else:
            d.insort(v)
    elif d.data[index] < v:
        d.update(index, v)
    elif d.data[index - 1] < v:
        d.update(index - 1, v)
    else:
        d.insort(v)
        
print(len(d.data))

Submission status: Wrong Answer

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 0
    
    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.data[index - 1] < v:
            d.update(index - 1, v)
        else:
            d.insort(v)
    elif d.data[index] < v:
        d.update(index, v)
    elif d.data[index - 1] < v:
        d.update(index - 1, v)
    else:
        d.insort(v)
        
print(len(d.data))

Submission status: Wrong Answer

Solution code:

def p_e():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = set([-1])

    for a in A:
        is_set = False
        for l in ans:
            if l < a:
                ans.remove(l)
                ans.add(a)
                is_set = True
                break

        if not is_set:
            ans.add(a)

    print(len(ans))


if __name__ == '__main__':
    p_e()

Submission status: Wrong Answer

Solution code:
def p_e():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = [-1]

    for a in A:
        is_set = False
        for i, l in enumerate(ans):
            if l < a:
                ans[i] = a
                is_set = True
                break

        if len(ans) > N / 2:
            continue

        if not is_set:
            ans.append(a)

    print(len(ans))


if __name__ == '__main__':
    p_e()