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: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import operator as op
import os
import sys
from bisect import bisect_left, bisect_right, insort
from functools import reduce
from io import BytesIO, IOBase
from itertools import chain, repeat, starmap

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


class SortedList:
    """Sorted list is a sorted mutable sequence."""

    DEFAULT_LOAD_FACTOR = 500

    def __init__(self, iterable=None):
        """Initialize sorted list instance."""
        self._len = 0
        self._load = self.DEFAULT_LOAD_FACTOR
        self._lists = []
        self._maxes = []
        self._index = []
        self._offset = 0
        if iterable is not None:
            self.update(iterable)

    def add(self, value):
        """Add `value` to sorted list."""
        _lists = self._lists
        _maxes = self._maxes
        if _maxes:
            pos = bisect_right(_maxes, value)
            if pos == len(_maxes):
                pos -= 1
                _lists[pos].append(value)
                _maxes[pos] = value
            else:
                insort(_lists[pos], value)
            self._expand(pos)
        else:
            _lists.append([value])
            _maxes.append(value)
        self._len += 1

    def _expand(self, pos):
        """Split sublists with length greater than double the load-factor."""
        _load = self._load
        _lists = self._lists
        _index = self._index

        if len(_lists[pos]) > (_load << 1):
            _maxes = self._maxes
            _lists_pos = _lists[pos]
            half = _lists_pos[_load:]
            del _lists_pos[_load:]
            _maxes[pos] = _lists_pos[-1]
            _lists.insert(pos + 1, half)
            _maxes.insert(pos + 1, half[-1])
            del _index[:]
        else:
            if _index:
                child = self._offset + pos
                while child:
                    _index[child] += 1
                    child = (child - 1) >> 1
                _index[0] += 1

    def update(self, iterable):
        """Update sorted list by adding all values from `iterable`."""
        _lists = self._lists
        _maxes = self._maxes
        values = sorted(iterable)

        if _maxes:
            if len(values) * 4 >= self._len:
                values.extend(chain.from_iterable(_lists))
                values.sort()
                self.clear()
            else:
                _add = self.add
                for val in values:
                    _add(val)
                return

        _load = self._load
        _lists.extend(values[pos:(pos + _load)]
                      for pos in range(0, len(values), _load))
        _maxes.extend(sublist[-1] for sublist in _lists)
        self._len = len(values)
        del self._index[:]

    def __contains__(self, value):
        """Return true if `value` is an element of the sorted list."""
        _maxes = self._maxes
        pos = bisect_left(_maxes, value)
        if pos == len(_maxes):
            return False

        _lists = self._lists
        idx = bisect_left(_lists[pos], value)
        return _lists[pos][idx] == value

    def remove(self, value):
        """Remove `value` from sorted list if it is a member."""
        _maxes = self._maxes
        pos = bisect_left(_maxes, value)
        if pos == len(_maxes):
            return

        _lists = self._lists
        idx = bisect_left(_lists[pos], value)
        if _lists[pos][idx] == value:
            self._delete(pos, idx)

    def _delete(self, pos, idx):
        """Delete value at the given `(pos, idx)`."""
        _lists = self._lists
        _maxes = self._maxes
        _index = self._index

        _lists_pos = _lists[pos]
        del _lists_pos[idx]
        self._len -= 1

        len_lists_pos = len(_lists_pos)
        if len_lists_pos > (self._load >> 1):
            _maxes[pos] = _lists_pos[-1]

            if _index:
                child = self._offset + pos
                while child > 0:
                    _index[child] -= 1
                    child = (child - 1) >> 1
                _index[0] -= 1
        elif len(_lists) > 1:
            if not pos:
                pos += 1
            prev = pos - 1
            _lists[prev].extend(_lists[pos])
            _maxes[prev] = _lists[prev][-1]
            del _lists[pos]
            del _maxes[pos]
            del _index[:]
            self._expand(prev)
        elif len_lists_pos:
            _maxes[pos] = _lists_pos[-1]
        else:
            del _lists[pos]
            del _maxes[pos]
            del _index[:]

    def _loc(self, pos, idx):
        """Convert an index pair (lists index, sublist index) into a single
        index number that corresponds to the position of the value in the
        sorted list."""
        if not pos:
            return idx

        _index = self._index
        if not _index:
            self._build_index()
        total = 0
        pos += self._offset
        while pos:
            if not pos & 1:
                total += _index[pos - 1]
            pos = (pos - 1) >> 1
        return total + idx

    def _pos(self, idx):
        """Convert an index into an index pair (lists index, sublist index)
        that can be used to access the corresponding lists position."""
        if idx < 0:
            last_len = len(self._lists[-1])
            if (-idx) <= last_len:
                return len(self._lists) - 1, last_len + idx
            idx += self._len
            if idx < 0:
                raise IndexError("list index out of range")
        elif idx >= self._len:
            raise IndexError("list index out of range")

        if idx < len(self._lists[0]):
            return 0, idx

        _index = self._index
        if not _index:
            self._build_index()

        pos = 0
        child = 1
        len_index = len(_index)
        while child < len_index:
            index_child = _index[child]
            if idx < index_child:
                pos = child
            else:
                idx -= index_child
                pos = child + 1
            child = (pos << 1) + 1
        return (pos - self._offset, idx)

    def _build_index(self):
        """Build a positional index for indexing the sorted list."""
        row0 = list(map(len, self._lists))
        if len(row0) == 1:
            self._index[:] = row0
            self._offset = 0
            return

        head = iter(row0)
        tail = iter(head)
        row1 = list(starmap(op.add, zip(head, tail)))
        if len(row0) & 1:
            row1.append(row0[-1])
        if len(row1) == 1:
            self._index[:] = row1 + row0
            self._offset = 1
            return

        size = 1 << (len(row1) - 1).bit_length()
        row1.extend(repeat(0, size - len(row1)))
        tree = [row0, row1]
        while len(tree[-1]) > 1:
            head = iter(tree[-1])
            tail = iter(head)
            row = list(starmap(op.add, zip(head, tail)))
            tree.append(row)
        reduce(list.__iadd__, reversed(tree), self._index)
        self._offset = size * 2 - 1

    def __delitem__(self, index):
        """Remove value at `index` from sorted list."""
        pos, idx = self._pos(index)
        self._delete(pos, idx)

    def __getitem__(self, index):
        """Lookup value at `index` in sorted list."""
        _lists = self._lists

        if self._len:
            if index == 0:
                return _lists[0][0]
            elif index == -1:
                return _lists[-1][-1]
        else:
            raise IndexError("list index out of range")

        if 0 <= index < len(_lists[0]):
            return _lists[0][index]

        len_last = len(_lists[-1])
        if -len_last < index < 0:
            return _lists[-1][len_last + index]

        pos, idx = self._pos(index)
        return _lists[pos][idx]

    def __iter__(self):
        """Return an iterator over the sorted list."""
        return chain.from_iterable(self._lists)

    def __reversed__(self):
        """Return a reverse iterator over the sorted list."""
        return chain.from_iterable(map(reversed, reversed(self._lists)))

    def __len__(self):
        """Return the size of the sorted list."""
        return self._len

    def bisect_left(self, value):
        """Return an index to insert `value` in the sorted list."""
        pos = bisect_left(self._maxes, value)
        return (self._len if pos == len(self._maxes) else self._loc(
            pos, bisect_left(self._lists[pos], value)))

    def bisect_right(self, value):
        """Return an index to insert `value` in the sorted list."""
        pos = bisect_right(self._maxes, value)
        return (self._len if pos == len(self._maxes) else self._loc(
            pos, bisect_right(self._lists[pos], value)))

    def count(self, value):
        """Return number of occurrences of `value` in the sorted list."""
        _maxes = self._maxes
        if not _maxes:
            return 0

        pos_left = bisect_left(_maxes, value)
        if pos_left == len(_maxes):
            return 0

        _lists = self._lists
        idx_left = bisect_left(_lists[pos_left], value)
        pos_right = bisect_right(_maxes, value)
        if pos_right == len(_maxes):
            return self._len - self._loc(pos_left, idx_left)

        idx_right = bisect_right(_lists[pos_right], value)
        if pos_left == pos_right:
            return idx_right - idx_left

        right = self._loc(pos_right, idx_right)
        left = self._loc(pos_left, idx_left)
        return right - left

    def __copy__(self):
        """Return a shallow copy of the sorted list."""
        return self.__class__(self)

    def pop(self, index=-1):
        """Remove and return value at `index` in sorted list."""
        if not self._len:
            raise IndexError("pop index out of range")

        _lists = self._lists
        if 0 <= index < len(_lists[0]):
            val = _lists[0][index]
            self._delete(0, index)
            return val

        len_last = len(_lists[-1])
        if -len_last < index < 0:
            pos = len(_lists) - 1
            loc = len_last + index
            val = _lists[pos][loc]
            self._delete(pos, loc)
            return val

        pos, idx = self._pos(index)
        val = _lists[pos][idx]
        self._delete(pos, idx)
        return val

    def index(self, value, start=0, stop=None):
        """Return first index of value in sorted list."""
        _len = self._len
        if start < 0:
            start += _len
        if start < 0:
            start = 0
        if stop is None:
            stop = _len
        if stop < 0:
            stop += _len
        if stop > _len:
            stop = _len

        if stop <= start:
            raise ValueError("{0!r} is not in list".format(value))

        _maxes = self._maxes
        pos_left = bisect_left(_maxes, value)
        if pos_left == len(_maxes):
            raise ValueError("{0!r} is not in list".format(value))

        _lists = self._lists
        idx_left = bisect_left(_lists[pos_left], value)
        if _lists[pos_left][idx_left] != value:
            raise ValueError("{0!r} is not in list".format(value))

        stop -= 1
        left = self._loc(pos_left, idx_left)
        if start <= left:
            if left <= stop:
                return left
        else:
            if start <= self.bisect_right(value) - 1:
                return start
        raise ValueError("{0!r} is not in list".format(value))

    def __add__(self, other):
        """Return new sorted list containing all values in both sequences."""
        values = reduce(list.__iadd__, self._lists, [])
        values.extend(other)
        return self.__class__(values)

    __radd__ = __add__

    def __iadd__(self, other):
        """Update sorted list with values from `other`."""
        self.update(other)
        return self

    def __mul__(self, num):
        """Return new sorted list with `num` shallow copies of values."""
        values = reduce(list.__iadd__, self._lists, []) * num
        return self.__class__(values)

    __rmul__ = __mul__

    def __imul__(self, num):
        """Update the sorted list with `num` shallow copies of values."""
        values = reduce(list.__iadd__, self._lists, []) * num
        self.clear()
        self.update(values)
        return self

    def __make_cmp(seq_op):
        "Make comparator method."

        def comparer(self, other):
            "Compare method for sorted list and sequence."
            self_len = self._len
            len_other = len(other)
            if self_len != len_other:
                if seq_op is op.eq:
                    return False
                if seq_op is op.ne:
                    return True

            for alpha, beta in zip(self, other):
                if alpha != beta:
                    return seq_op(alpha, beta)
            return seq_op(self_len, len_other)

        comparer.__name__ = "__{0}__".format(seq_op.__name__)
        return comparer

    __eq__ = __make_cmp(op.eq)
    __ne__ = __make_cmp(op.ne)
    __lt__ = __make_cmp(op.lt)
    __gt__ = __make_cmp(op.gt)
    __le__ = __make_cmp(op.le)
    __ge__ = __make_cmp(op.ge)
    __make_cmp = staticmethod(__make_cmp)

    def __repr__(self):
        """Return string representation of sorted list."""
        return "SortedList({0})".format(reduce(list.__iadd__, self._lists, []))


def main():
    n = int(input())

    s = SortedList()

    for i in range(n):
        ai = int(input())
        d = s.bisect_left(ai)

        if d <= len(s) and d != 0 and s[d - 1] < ai:
            s.remove(s[d - 1])

        s.add(ai)

    print(len(s))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
from collections import deque

def main():
    _ = int(input())
    A = list(map(int, sys.stdin.readlines()))
    
    arr = deque()
    arr.append(A[0])
    for a in A[1:]:
        if a <= arr[0]:
            arr.appendleft(a)
        else:
            insert_index = bisect.bisect_left(arr, a)
            update = max(0, insert_index-1)
            arr[update] = a
    print(len(arr))
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

S = [0] * N

end = N
for i in range(N):
    j = bisect.bisect_left(S, A[i], end, N)
    if j <= end:
        S[j-1] = A[i]
        end -= 1
    else:
        S[j-1] = A[i]

print(N-end)

Submission status: Accepted

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

import bisect
min_list = [-1]
for i in reversed(range(n)):
    if a[i] >= min_list[-1]:
        min_list.append(a[i])
    else:
        insert_index = bisect.bisect_right(min_list, a[i])
        min_list[insert_index] = a[i]
    # print(a[i], min_list)


print(len(min_list) - 1)

Submission status: Accepted

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

from bisect import bisect_left, bisect_right

def lis(a):
    length = [a[0]]
    for i in range(1, len(a)):
        if a[i] >= length[-1]:
            length.append(a[i])
        else:
            length[bisect_right(length, a[i])] = a[i]
    return len(length)


print(lis(a))

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
List = [-A[0]]
for i in range(1, N):
    if -List[-1]>=A[i]:
        List.append(-A[i])
    else:
        index = bisect.bisect_right(List, -A[i])
        List[index] = -A[i]
print(len(List))

Submission status: Accepted

Solution code:
import bisect

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

C, Ci = [-1] * (N - 1) + [A[0]], N - 1


for i in range(1, N):
    bA = bisect.bisect_left(C, A[i])
    if bA == Ci:
        Ci -= 1
        C[Ci] = A[i]
    else:
        C[bA - 1] = A[i]

print(N - Ci)

Submission status: Accepted

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

"""
import random
N=10
A=[random.randint(1,10) for i in range(N)]
print(A)
"""

import bisect
from collections import deque
D=deque([A[0]])

for a in A[1:]:
    if a<=D[0]:
        D.appendleft(a)

    else:
        x = bisect.bisect_right(D,a-1)
        D[x-1]=a

    #print(D)

print(len(D))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import bisect
import sys

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def d(n):
    divisors = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    return divisors


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

    res = [A[-1]]  # 4,5,9,,,
    for ai in reversed(A[:-1]):
        if ai >= res[-1]:
            res.append(ai)
            continue
        ind = bisect.bisect_right(res, ai)
        res[ind] = ai
    print(len(res))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect


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

    colors = [-a[0]]
    for aa in a[1:]:
        i = bisect.bisect_right(colors, -aa)
        if i == len(colors):
            colors.append(-aa)
        else:
            colors[i] = -aa
    print(len(colors))


main()

Submission status: Accepted

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

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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

seq = deque()
for a in A:
    i = bisect.bisect_left(seq, a)
    if i == 0:
        seq.appendleft(a)
    else:
        seq[i - 1] = a
        while i < len(seq) and seq[i - 1] > seq[i]:
            seq[i], seq[i - 1] = seq[i - 1], seq[i]
            i += 1
print(len(seq))

Submission status: Accepted

Solution code:
n=int(input())
tail=[int(input())]
import bisect
from collections import deque
tail=deque(tail)
c=1
for i in range(n-1):
    a=int(input())
    p=bisect.bisect_left(tail,a)
    if p==0:
        tail.appendleft(a)
        c+=1
    else:
        tail[p-1]=a
print(c)

Submission status: Accepted

Solution code:
def reverse_bisect(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return lo

N = int(input())
color_list = []
color_len = 0
for i in range(N):
    a = int(input())
    index = reverse_bisect(color_list, a, 0, color_len)
    if(index == color_len):
        color_list.append(a)
        color_len += 1
    else:
        color_list[index] = a
print(color_len)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n = i()
a = hi(n)
ans = 1
D = deque()
D.append(a[0])
for i in range(1, n):
    index = bisect_left(D, a[i])
    if 0 == index:
        D.appendleft(a[i])
    else:
        D[index - 1] = a[i]
print(len(D))

Submission status: Accepted

Solution code:
from collections import deque

def replace(l, a, max_idx, min_idx):
    if max_idx == min_idx:
        l[max_idx] = a
        return

    center = (max_idx + min_idx)//2
    if l[center] >= a:
        return replace(l, a, max_idx, center+1)
    else:
        return replace(l, a, center, min_idx)


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


l = []

for a in A:
    if len(l) == 0:
        l.append(a)
    elif l[-1] >= a:
        l.append(a)
    else:
        replace(l, a, len(l)-1, 0)

print(len(l))

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
q=[-1 for _ in range(n)]
for i in range(n):
    x=a[i]
    idx = bisect.bisect_left(q,x)
    q[idx-1]=x
print(n-bisect.bisect_right(q,-1))

Submission status: Accepted

Solution code:
def reverse_insort(a, x):
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo


n = int(input())

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

for i in range(n - 1):
    t = int(input())
    ch = 0
    if t <= ans[-1]:
        ans.append(t)
    else:
        ans[reverse_insort(ans, t)] = t

print(len(ans))

Submission status: Accepted

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


def Solve():
    L=[]
    N=int(input())
    for i in range(N):
        L.append(int(input()))

    col=1
    K=deque()
    
    
    for i,a in enumerate(L):
        if i==0:
            K.append(a)
            continue
        pos=bisect.bisect_left(K,a)
        if pos==0:
            col+=1
            K.appendleft(a)
        else:
            K[pos-1]=a

    return col



print(Solve())

Submission status: Accepted

Solution code:
N = int(input())
C = [-1]
for _ in range(N):
  a = int(input())
  s = 0
  t = len(C) - 1
  if a > C[0]:
    C[0] = a
    continue
  if C[-1] >= a:
    C.append(a)
    continue
  while t - s > 1:
    m = (t + s) // 2
    if a > C[m]:
      t = m
    else:
      s = m
  C[t] = a
print(len(C))

Submission status: Accepted

Solution code:
import collections
import sys
import bisect
input = sys.stdin.readline
N = int(input())
queue = collections.deque()
queue.append(int(input()))
for i in range(N-1):
    a = int(input())
    index = bisect.bisect_left(queue, a)
    if index == 0:
        queue.appendleft(a)
    else:
        queue[index-1] = a

print(len(queue))

Submission status: Accepted

Solution code:
N = int(input())
A = list(int(input())for i in range(N))
H = [A[0]]
for i in range(1,N):
    if A[i] <= H[-1]:
        H.append(A[i])
    else:
        l,r =0,len(H)
        while l != r :
            if H[(l+r)//2]>=A[i]:
                l = (l+r)//2+1
            else:
                r = (l+r)//2
        H[l] = A[i]
print(len(H))

Submission status: Accepted

Solution code:
from collections import deque
import bisect

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

colors = deque([A[0]])
for a in A[1:]:
    i = bisect.bisect_left(colors, a)
    if i != 0:
        colors[i - 1] = a
    else:
        colors.appendleft(a)

print(len(colors))

Submission status: Accepted

Solution code:
import bisect
from collections import deque
n = int(input())
c = deque()
for i in range(n):
    a = int(input())
    idx = bisect.bisect_left(c,a)
    if idx == 0:
        c.appendleft(a)
    else:
        c[idx-1] = a
print(len(c))

Submission status: Accepted

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

dq = deque()
for i in range(n):
    a = int(input())
    index = bisect.bisect_left(dq, a)
    if index == 0:
        dq.appendleft(a)
    else:
        dq[index-1] = a
print(len(dq))

Submission status: Accepted

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

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

group_min = [a.pop()]
a.reverse()

for e in a:
    idx = bisect.bisect(group_min, e)
    if len(group_min) == idx:
        group_min.append(e)
    elif group_min[idx] > e:
        group_min[idx] = e
    else:
        # group_min[idx] == e:
        group_min.insert(idx, e)

print(len(group_min))

Submission status: Accepted

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

vals = []
for _ in range(n):
	a = - int(input())
	idx = bisect(vals,a)
	if idx == len(vals):
		vals.append(a)
	else:
		vals[idx]=a

print(len(vals))

Submission status: Accepted

Solution code:
from bisect import bisect_right
import sys
input=sys.stdin.readline
n=int(input())
A=[-int(input())-1 for _ in range(n)]
M=[0]*n
for a in A:
    idx=bisect_right(M,a)
    M[idx]=a
ans=0
for m in M:
    if m:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys,heapq,math,resource,bisect
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  #resource.setrlimit(RLIMIT_STACK, (128*1024*1024,hard))

n = inn()
a = []
for i in range(n):
    a.append(inn())
b = [a[n-1]]
for i in range(n-2,-1,-1):
    if a[i]>=b[-1]:
        b.append(a[i])
    else:
        j = bisect.bisect_right(b,a[i])
        b[j] = a[i]
    #ddprint(b)
print(len(b))

Submission status: Accepted

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


b = []

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[-1]:
            b.append(ai)
        else:
            l = -1
            r = len(b)
            mid = (l + r) // 2
            while (r - l > 1):
                mid = (l + r) // 2
                if b[mid] >= ai:
                    l = mid
                else:
                    r = mid
            b[r] = ai

print(len(b))

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = [0]*N
for i in range(N):
    A[i] = int(input())
C = []
for a in A:
    k = bisect.bisect_right(C,-a)
    if k >= len(C):
        C.append(-a)
    else:
        C[k] = -a
print(len(C))

Submission status: Accepted

Solution code:
def bis(l,target,start, end):
    while(start<end):
        mid = (start + end )//2
        if target > l[mid]:
            end = mid
        else:
            start = mid + 1
    return start

l = []
n = int(input())
for i in range(n):
    x = int(input())
    if l == []:
        l.append(x)
    else:
        idx = bis(l,x,0,len(l)-1)
        #print(l)
        #print(x,idx)
        if x > l[idx]:
            l[idx] = x
        else:
            l.append(x)
#print(l)
print(len(l))

Submission status: Accepted

Solution code:
def hersCode(L, n):
  ok = len(L)
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] < n:
      ok = mid
    else:
      ng = mid
  return ok


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

L = [-1]
for i in range(N):
  t = hersCode(L, A[i])
  if t == len(L) - 1:
    L[-1] = A[i]
    L.append(-1)
  else:
    L[t] = A[i]

print(len(L) - 1)

Submission status: Accepted

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


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    stream = []
    for a in A:
        idx = bisect_right(stream, -a)
        if idx < len(stream):
            stream[idx] = -a
        else:
            stream.append(-a)

    print(len(stream))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def LIS(seq):
    import bisect
    dp = [seq[0]]
    for s in seq[1:]:
        if s >= dp[-1]:
            dp.append(s)
        else:
            dp[bisect.bisect_right(dp,s)] = s
    return len(dp)
assert(LIS([2,2,1,4,1,5,1,1,1])==5)

print(LIS(_A))