Slide_Maximum.py

• View this file on GitHub
• Last update: 2023-06-18 16:52:58+09:00

Code

from collections import deque

def Slide_Maximum_Index(A, k):
    """リストA の k 要素スライド最大値をもつインデックスを求める.

    [Input]
    A: List
    k: Length

    [Output]
    M: 長さ |A|-k+1 のリストで, 第 i 要素は max(A[i], ..., A[i+k-1])=A[M[i]] となるようになる.
    """

    N=len(A)
    index=[0]*N
    Q=deque()

    for i in range(N):
        while Q and Q[0]<=i-k:
            Q.popleft()

        while Q and A[Q[-1]]<A[i]:
            Q.pop()
        Q.append(i)
        index[i]=Q[0]
    return index

def Slide_Maximum_Value(A, k):
    """リストA の k 要素スライド最大値を求める.

    [Input]
    A: List
    k: Length

    [Output]
    M: 長さ |A|-k+1 のリストで, 第 i 要素は max(A[i], ..., A[i+k-1])=A[M[i]] となるようになる.
    """

    N=len(A)
    res=[0]*N
    Q=deque()

    for i in range(N):
        while Q and Q[0]<=i-k:
            Q.popleft()

        while Q and A[Q[-1]]<A[i]:
            Q.pop()
        Q.append(i)
        res[i]=A[Q[0]]
    return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page