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:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpln(n)[::-1]
x = []
heapify(x)
for i,j in enumerate(a):
    if i == 0:
        heappush(x,-j)
        continue
    m = -heappop(x)
    if j >= m:
        heappush(x,-j)
        heappush(x,-m)
    else:
        heappush(x,-j)
print(len(x))

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpln(n)[::-1]
res = 0
x = []
heapify(x)
for i,j in enumerate(a):
    if i == 0:
        heappush(x,-j)
        res += 1
        continue
    m = -heappop(x)
    if j > m:
        res += 1
        heappush(x,-j)
        heappush(x,-m)
    else:
        heappush(x,-j)
print(len(x))

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpln(n)[::-1]
res = 0
x = []
heapify(x)
for i,j in enumerate(a):
    if i == 0:
        heappush(x,-j)
        res += 1
        continue
    m = -heappop(x)
    if j > m:
        res += 1
        heappush(x,-j)
        heappush(x,-m)
    else:
        heappush(x,-j)
    
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpln(n)
res = 0
m = 0
for i,j in enumerate(a):
    if i == 0:
        m = j
        res += 1
        continue
    if j <= m:
        res += 1
        m = j
print(res)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a = sorted([int(input()) for i in range(n)])
LIS = [a[0]]
for i in range(len(a)):
    if a[i] >= LIS[-1]:
        LIS.append(a[i])
    else:
        LIS[bisect.bisect_left(LIS, a[i])] = a[i]
print(len(LIS)-1)

Submission status: Wrong Answer

Solution code:
import bisect

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

Submission status: Wrong Answer

Solution code:

def bisect_desc(a,x):
    r = len(a)
    if r == 0:
        return 0
    l = 0
    while l != r:
        f = (l+r)//2
        if a[f] >= x:
            l = f+1
        else:
            r = f
    return l

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as left 
import sys
readline = sys.stdin.buffer.readline

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

INF = 10**10
dp = [INF] * (N+1)

answer = 0
for a in A:
  l = left(dp, a)
  if l == 0:
    answer += 1
  dp[l] = a
print(answer)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True
ans=0
n=I()
a=[]
for i in range(n):
    a.append(I())
c=0
mm=0
for j in a[::-1]:
    if j>=mm:
        mm=j
        c+=1
print(c)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

import bisect

answer = 0
color = []
append = color.append
for i in range(N):
    index = bisect.bisect_left(color, A[i])
    if index == 0:
        bisect.insort_left(color, A[i])
        answer += 1
    else:
        if index == len(color):
            color[-1] = A[i]
        else:
            if color[index] == A[i]:
                index -= 1
            tmp = color.pop(index)
            bisect.insort_left(color, A[i])

print(answer)

Submission status: Wrong Answer

Solution code:
import bisect


def sequence_decomposing(N: int, A: list)->int:
    mins = [A[0]]

    for a in A[1:]:
        i = bisect.bisect_left(mins, a)
        if i == 0:
            mins = [a] + mins
        mins[i-1] = a

    return len(mins)


if __name__ == "__main__":
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = sequence_decomposing(N, A)
    print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque

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

LDS = deque()
LDS.append(A[0])

for i in range(1,N):
    if LDS[0] >= A[i]:
        LDS.appendleft(A[i])
    else:
        LDS[bisect.bisect(LDS,A[i])-1] = A[i]

print(len(LDS))

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n=int(input())
x=[-1]*n
for _ in range(n):
    a=int(input())
    i=bisect(x,a)-1
    x[i]=a
print(n-x.count(-1))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque

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

L = deque()
L.append(A[0])
for i in range(1, N):
    if A[i] <= L[0]:
        L.appendleft(A[i])
    elif A[i] > L[-1]:
        L[-1] = A[i]
    else:
        idx = bisect.bisect_left(L, A[i])
        L[idx] = A[i]
        
print(len(L))

Submission status: Wrong Answer

Solution code:
import bisect


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

L = []
L.append(A[0])
for i in range(1, N):
    if A[i] <= L[0]:
        L = [A[i]] + L
    elif A[i] > L[-1]:
        L[-1] = A[i]
    else:
        idx = bisect.bisect_left(L, A[i])
        L[idx] = A[i]
        
print(len(L))

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
for i in a[n-2::-1]:
  if c[-1] <= i:
    c.append(i)
  else:
    c[bisect.bisect_left(c,i)] = i
print(len(c))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=[]
lstm=0
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if not lst:count+=1
        continue
    flag=1
    for l in range(len(lst)):
        if lst[l]<A[i]:
            lst[l]=A[i]
            flag=0
            break
    if flag:
        lst.append(A[i])
        count+=1
    #print(count,i,lst)
print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=[]
lstm=0
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        continue
    flag=1
    for l in range(len(lst)):
        if lst[l]<A[i]:
            lst[l]=A[i]
            flag=0
            break
    if flag:
        lst.append(A[i])
        count+=1
    #print(count,i,lst)
print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input()) for _ in range(N)]
k=1
c=1
for i in range(1,N):
    if A[i]>A[i-1]:
        k=1
    else:
        k+=1
        c=max(c,k)
print(c)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input()) for _ in range(N)]
k=1
c=1
for i in range(1,N):
    if A[i]>A[i-1]:
        k=1
    else:
        k+=1
        c=max(c,k)
print(k)

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
c = [int(input())]
for i in range(n-1):
  a = int(input())
  if c[0] >= a:
    c = [0] + c
  else:
    c[bisect.bisect_right(c,a)-1] = a
print(len(c))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def LIS(seq, wider_sense=False):
    from bisect import bisect_left
    ｄｐ = [seq[0]]
    for i in seq[1:]:
        if wider_sense and i >= dp[-1]:
            dp.append(i)
        elif not wider_sense and i > dp[-1]:
            dp.append(i)
        else:
            dp[bisect_left(dp, i)] = i
    return len(dp)
  
N = int(input())
A = [int(input()) for _ in range(N)]
print(LIS([-a for a in A], True))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def LIS(li):
    lis_li = [li[0]]
    for i in li[1:]:
        # 同値がNGの時は=を外す
        if i >= lis_li[-1]:
            lis_li.append(i)
        else:
            lis_li[bisect_left(lis_li, i)] = i
    return len(lis_li)
  
N = int(input())
A = [int(input()) for _ in range(N)]
# リストを逆順にして単調減少最大を計算
print(LIS(A[::-1]))

Submission status: Wrong Answer

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

minA = A[0]
ans = 1
for i in range(1, N):
    if A[i] <= minA:
        ans += 1
        minA = A[i]
print(ans)

Submission status: Wrong Answer

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

n = int(input())
A = [int(input()) for _ in range(n)]
color_box = []  # 色毎に今塗っている最大の数字をもつ

num = -1
for a in A:
    if a > num:
        num = a

    else:
        heapq.heappush(color_box, num)
        num = heapq.heappop(color_box)

        if a > num:
            num = a
        else:
            heapq.heappush(color_box, num)
            num = a

print(len(color_box)+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
W = []
L = [0]*N
for i in range(N):
    w = int(input())
    W.append(w)
for i in range(N):
    p = -1
    m = 0
    for j in range(N):
        if W[i] > L[j]:
            m = max(m,L[j])
            if m == L[j]:
                p = j
    L[p] = W[i]

ans = N - L.count(0)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

def main():    
    N = int(input())
    A = [int(input()) for i in range(N)]
    n = [A.pop(-1)]
    A.reverse()
    
    for a in A:
        if n[-1] <= a: n.append(a)
        else: n[bisect_left(n, a-1)] = a
    
    print(len(n))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

def main():    
    N = int(input())
    A = [int(input()) for i in range(N)]
    n = [A.pop(-1)]
    A.reverse()
    
    for a in A:
        if n[-1] <= a: n.append(a)
        else: n[bisect_left(n, a)] = a
    
    print(len(n))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(input()) for i in range(n)]
a.reverse()
m=0
ans=0
for i in range(n):
  if a[i]>=m:
    ans+=1
    m=a[i]
print(ans)

Submission status: Wrong Answer

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

a=[int(input()) for _ in range(n)]
x=[a[0]]
for i in a[1:]:
  y=bisect.bisect(x,i)
  if y==len(x):x.append(i)
  else:x[y]=i
print(len(x))

Submission status: Wrong Answer

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

ans = 0
mx = -1
for i in range(n-1, -1, -1):
    if A[i] >= mx:
        ans += 1
        mx = A[i]

print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Q = [-float("inf"), A[0]] + [float("inf")] * (n+1)
le = 2
for i in range(1, n):
    if Q[le-1] >= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        l = 0
        r = le
        m = (l+r)//2
        while r-l > 1:
            if Q[m] > A[i]:
                l = m
            else:
                r = m
            m = (l+r)//2
        Q[l+1] = A[i]
    # print(Q[:10])

print(le-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(input())+1 for i in range(n)]

Q = [-float("inf"), A[0]] + [float("inf")] * (n+1)
le = 2
for i in range(1, n):
    if Q[le-1] >= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        l = 0
        r = le
        m = (l+r)//2
        while r-l > 1:
            if Q[m] > A[i]:
                r = m
            else:
                l = m
            m = (l+r)//2
        Q[l+1] = A[i]

print(le-1)

Submission status: Wrong Answer

Solution code:
import bisect

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


colors = []
cmt = 0
#後ろから見ていく
for i,n in enumerate(list(reversed(A))):
    # 一つ目はとりあえずなんか一色ぬる
    if i == 0:
        colors.append(n)
    else:
        #二つ目以降は、各色の最小値のなかで、今見ているのより小さいものがあればそれを置き換える
        idx = bisect.bisect_left(colors, n)
        if idx == len(colors):
            colors.append(n)
        else:
            if colors[idx] == n:
                colors.insert(idx, n)
            else:
                colors[idx] = n

print(len(colors))

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
l = [0 for i in range(n)]
for i in range(n):
    a1 = int(input())
    l[n-1-i] = a1
h = [l[0]]
ans = 1
for i in range(1,n):
    a = bisect.bisect_left(h,l[i])
    if ans == a:
        ans += 1
        h.append(l[i])
    elif a == 0:
        if h[0] == l[i]:
            h.append(l[i])
            ans += 1
        else:
            h[0] = l[i]
    else:
        h[a] = l[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N=int(input())
A=[int(input()) for i in range(N)]
#A=[2000000+i if i%2==1 else 2000000-i for i in range(100000)]
#N=len(A)
lst=[A[-1]]
nowN=max(A)+1
i=len(A)-2
#maxA=0
while i>=0:
    #print(i)
    #print(lst)
    if max(lst)>A[i]:
        lst[bisect.bisect_left(lst,A[i])]=A[i]
                #break
    else:
        lst.insert(bisect.bisect_left(lst,A[i]),A[i])
        #maxA=A[i]

    i-=1
print(len(lst))

Submission status: Wrong Answer

Solution code:
import bisect

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

Submission status: Wrong Answer

Solution code:
import bisect

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

Submission status: Wrong Answer

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

print(count)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input())for i in range(N)]
m = A[0]
ans = 1
for i in A[1:]:
    if i <= m:
        m = i
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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


def main():
    N = int(input())
    minA = int(input())
    ans = 1
    for _ in range(N-1):
        A = int(input())
        if A <= minA:
            ans += 1
            minA = A
    print(ans)


if __name__ == '__main__': main()

Submission status: Wrong Answer

Solution code:
import bisect

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

for i in range(n):
    a.append(int(input()))

a.reverse()
cnt = 0
for i in range(1,n):
    if a[i] + cnt == a[i-1]:
        cnt += 1
    a[i] += cnt
        
INF = 10000000000
dp = [INF] * n

for i in range(n):
    t = bisect.bisect_left(dp,a[i])
    if t != n:
        dp[t] = a[i]

print(bisect.bisect_left(dp,INF))

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
c = []

for i in range(n):
    c.append(int(input()))

c.reverse()
cnt = 0
for i in range(1,n):
    if c[i] + cnt == c[i-1]:
        cnt += 1
    c[i] += cnt
        
INF = 100000000
dp = [INF] * n

for i in range(n):
    t = bisect.bisect_left(dp,c[i])
    if t != n:
        dp[t] = c[i]

print(bisect.bisect_left(dp,INF))

Submission status: Wrong Answer

Solution code:
# ABC134E - Sequence Decomposing
def lis(A: "Array[int]") -> int:
    from bisect import bisect_left

    # dp := length of LIS (dp table itself is not LIS)
    dp = [A[0]]
    for i in A[1:]:
        if i > dp[-1]:
            dp.append(i)
        else:
            dp[bisect_left(dp, i)] = i
    return len(dp)


def main():
    N, *A = map(int, open(0).read().split())
    ans = lis([-i for i in A])  # need the length of lds -> -i
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC134E - Sequence Decomposing
def lis(A: "Array[int]") -> int:
    from bisect import bisect_left

    # dp := length of LIS (dp table itself is not LIS)
    dp = [A[0]]
    for i in A[1:]:
        if i >= dp[-1]:
            dp.append(i)
        else:
            dp[bisect_left(dp, i)] = i
    return len(dp)


def main():
    N, *A = map(int, open(0))
    ans = lis(A[::-1])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC134E - Sequence Decomposing
def lis(A: "Array[int]") -> int:
    from bisect import bisect_left

    # dp := length of LIS (dp table itself is not LIS)
    dp = [A[0]]
    for i in A[1:]:
        if i >= dp[-1]:
            dp.append(i)
        else:
            dp[bisect_left(dp, i)] = i
    return len(dp)


def main():
    N, *A = map(int, open(0))
    ans = lis([-i for i in A])  # need the length of lds -> -i
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
M = 10 ** 10

for _ in range(N):
    a = int(input())
    if a <= M:
        ans += 1
        M = a

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
#a=[int(i) for i in input().split()]
a=[]
ans=1
chk=int(input())
for i in range(n-1):
    x=int(input())
    if x<=chk: ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush 
n=int(input())
a=[int(input()) for _ in range(n)]
num=[-a[0]]
count=1
lst=[a[0]]
for i in range(1,n):
    b=-num[0]
    if a[i]>b:
        heappush(num,-a[i])
    else:
        c=heappop(lst)
        if a[i]>c:
            heappush(lst,a[i])
        else:
            heappush(lst,c)
            heappush(lst,a[i])
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush 
n=int(input())
a=[int(input()) for _ in range(n)]
num=a[0]
count=1
lst=[a[0]]
for i in range(1,n):
    if a[i]>num:
        num=a[i]
    else:
        heappush(lst,num)
        c=heappop(lst)
        if a[i]>c:
            heappush(lst,a[i])
        else:
            heappush(lst,c)
            heappush(lst,a[i])
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n = int(input())
xs = [int(input()) for _ in range(n)]
d = {}
for i, x in enumerate(sorted(xs)):
    d[x] = i

segtree = SegTree([0]*n, n, 0, max)
r = 0
for x in xs:
    xi = d[x]
    y = segtree.query(xi+1, n)
    segtree.update(xi, y+1)
    r = max(r, y+1)
print(r)

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import bisect_left

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

q = deque([A[0]])

for x in A[1:]:
    i = bisect_left(q,x)
    if i == 0:q.appendleft(x)
    else:q[i-1]=x
    print(q)
print(len(q))

Submission status: Wrong Answer

Solution code:
import bisect

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
Q = [-a[0]]
for i in range(1,n):
    if a[i] <= -Q[-1]:
        Q.append(-a[i])
    else:
        j = bisect.bisect_left(Q,-a[i])
        #print(a,Q,i,j)
        Q[j] = -a[i] 
    #print(i,Q)
print(len(Q))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = IR(n)
IS = deque([L[0]])
for i in range(1, n):
    if L[i] <= IS[0]:
        IS.appendleft(i)
    else:
        IS[bisect_left(IS, L[i]) - 1] = L[i]



print(len(IS))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[0]*N
for i in range(N):
  A[i]=int(input())
m=A[0]
M=m
c=1
for a in A[1:]:
  if a<=m:
    c+=1
    m=a
  elif M<a:
    M=a
print(c)

Submission status: Wrong Answer

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

ans = 0
l, r = 0, 0
while r < N - 1:
    if A[r + 1] <= A[r]:
        r += 1
        ans = max(ans, r - l + 1)
    else:
        r += 1
        l = r
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right, bisect_left

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

dp = [1]*N

for a in A:
    ia = bisect_right(dp, -a)
    if dp[ia] == 1:
        dp[ia] = -a
    else:
        ib = bisect_left(dp, -a)
        dp[ib] = -a

ans = 0
for i in range(N):
    if dp[i] != 1:
        ans += 1
print(ans)