cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: test/atcoder/agc/agc038_b_sliding_min_max.test.py

Depends on

Code

# verification-helper: PROBLEM https://atcoder.jp/contests/agc038/tasks/agc038_b

from cp_library.alg.graph.perm_graph_cls import PermGraph

def main():
    N, K = read(tuple[int,int])
    P = read(PermGraph[N,0])
    win = SlidingMinMax(maxlen=K)
    win.extend(P[:K])
    ans = 1 - (unchanged := len(win.minq) == K)
    for i in range(K,N):
        p = win.popleft()
        win.append(P[i])
        unchanged |= (is_sorted:=len(win.minq) == K)
        ans += not is_sorted and (p > win.min or P[i] < win.max)
        
    ans += unchanged
    write(ans)
    
from cp_library.ds.slidingminmax_cls import SlidingMinMax
from cp_library.io.read_fn import read
from cp_library.io.write_fn import write

if __name__ == "__main__":
    main()
# verification-helper: PROBLEM https://atcoder.jp/contests/agc038/tasks/agc038_b

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''


from math import gcd
from typing import Iterable

import typing
from collections import deque
from numbers import Number
from types import GenericAlias 
from typing import Callable, Collection, Iterator, Union
import os
import sys
from io import BytesIO, IOBase


class FastIO(IOBase):
    BUFSIZE = 8192
    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):
        BUFSIZE = self.BUFSIZE
        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):
        BUFSIZE = self.BUFSIZE
        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):
    stdin: 'IOWrapper' = None
    stdout: 'IOWrapper' = None
    
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable

    def write(self, s):
        return self.buffer.write(s.encode("ascii"))
    
    def read(self):
        return self.buffer.read().decode("ascii")
    
    def readline(self):
        return self.buffer.readline().decode("ascii")

sys.stdin = IOWrapper.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper.stdout = IOWrapper(sys.stdout)
from typing import TypeVar
_T = TypeVar('T')

class TokenStream(Iterator):
    stream = IOWrapper.stdin

    def __init__(self):
        self.queue = deque()

    def __next__(self):
        if not self.queue: self.queue.extend(self._line())
        return self.queue.popleft()
    
    def wait(self):
        if not self.queue: self.queue.extend(self._line())
        while self.queue: yield
 
    def _line(self):
        return TokenStream.stream.readline().split()

    def line(self):
        if self.queue:
            A = list(self.queue)
            self.queue.clear()
            return A
        return self._line()
TokenStream.default = TokenStream()

class CharStream(TokenStream):
    def _line(self):
        return TokenStream.stream.readline().rstrip()
CharStream.default = CharStream()


ParseFn = Callable[[TokenStream],_T]
class Parser:
    def __init__(self, spec: Union[type[_T],_T]):
        self.parse = Parser.compile(spec)

    def __call__(self, ts: TokenStream) -> _T:
        return self.parse(ts)
    
    @staticmethod
    def compile_type(cls: type[_T], args = ()) -> _T:
        if issubclass(cls, Parsable):
            return cls.compile(*args)
        elif issubclass(cls, (Number, str)):
            def parse(ts: TokenStream): return cls(next(ts))              
            return parse
        elif issubclass(cls, tuple):
            return Parser.compile_tuple(cls, args)
        elif issubclass(cls, Collection):
            return Parser.compile_collection(cls, args)
        elif callable(cls):
            def parse(ts: TokenStream):
                return cls(next(ts))              
            return parse
        else:
            raise NotImplementedError()
    
    @staticmethod
    def compile(spec: Union[type[_T],_T]=int) -> ParseFn[_T]:
        if isinstance(spec, (type, GenericAlias)):
            cls = typing.get_origin(spec) or spec
            args = typing.get_args(spec) or tuple()
            return Parser.compile_type(cls, args)
        elif isinstance(offset := spec, Number): 
            cls = type(spec)  
            def parse(ts: TokenStream): return cls(next(ts)) + offset
            return parse
        elif isinstance(args := spec, tuple):      
            return Parser.compile_tuple(type(spec), args)
        elif isinstance(args := spec, Collection):  
            return Parser.compile_collection(type(spec), args)
        elif isinstance(fn := spec, Callable): 
            def parse(ts: TokenStream): return fn(next(ts))
            return parse
        else:
            raise NotImplementedError()

    @staticmethod
    def compile_line(cls: _T, spec=int) -> ParseFn[_T]:
        if spec is int:
            fn = Parser.compile(spec)
            def parse(ts: TokenStream): return cls([int(token) for token in ts.line()])
            return parse
        else:
            fn = Parser.compile(spec)
            def parse(ts: TokenStream): return cls([fn(ts) for _ in ts.wait()])
            return parse

    @staticmethod
    def compile_repeat(cls: _T, spec, N) -> ParseFn[_T]:
        fn = Parser.compile(spec)
        def parse(ts: TokenStream): return cls([fn(ts) for _ in range(N)])
        return parse

    @staticmethod
    def compile_children(cls: _T, specs) -> ParseFn[_T]:
        fns = tuple((Parser.compile(spec) for spec in specs))
        def parse(ts: TokenStream): return cls([fn(ts) for fn in fns])  
        return parse
            
    @staticmethod
    def compile_tuple(cls: type[_T], specs) -> ParseFn[_T]:
        if isinstance(specs, (tuple,list)) and len(specs) == 2 and specs[1] is ...:
            return Parser.compile_line(cls, specs[0])
        else:
            return Parser.compile_children(cls, specs)

    @staticmethod
    def compile_collection(cls, specs):
        if not specs or len(specs) == 1 or isinstance(specs, set):
            return Parser.compile_line(cls, *specs)
        elif (isinstance(specs, (tuple,list)) and len(specs) == 2 and isinstance(specs[1], int)):
            return Parser.compile_repeat(cls, specs[0], specs[1])
        else:
            raise NotImplementedError()

class Parsable:
    @classmethod
    def compile(cls):
        def parser(ts: TokenStream): return cls(next(ts))
        return parser

class FuncGraph(list[int], Parsable):
    def __init__(F, successors):
        super().__init__(successors)
        F.N = F.M = len(F)

    def find_cycle(P, root: int) -> list[int]:
        slow = fast = root
        while (slow := P[slow]) != (fast := P[P[fast]]): pass
        cyc = [slow]
        while P[slow] != fast: cyc.append(slow := P[slow])
        return cyc
    
    def cycles(P) -> 'CRFList[int]':
        vis, cycs, S = u8f(N := P.N), elist(N), elist(N)
        for v in range(P.N):
            if vis[v]: continue
            slow = fast = v
            while (slow := P[slow]) != (fast := P[P[fast]]) and not vis[fast]: pass
            if vis[fast]: continue
            S.append(len(cycs))
            cycs.append(slow)
            vis[slow := P[slow]] = 1
            while slow != fast:
                cycs.append(slow)
                vis[slow := P[slow]] = 1
        return CRFList(cycs, S)
    
    def chain(P, root):
        cyc = P.find_cycle(root)
        slow, fast = root, cyc[0]
        if slow == fast: return [], cyc
        line = [slow]
        while (slow := P[slow]) != (fast := P[fast]):
            line.append(slow)
        return line, roll(cyc, -cyc.index(slow))

    @classmethod
    def compile(cls, N: int, shift = -1):
        return Parser.compile_repeat(cls, shift, N)


from typing import Generic

class CRFList(Generic[_T]):
    def __init__(crf, A: list[_T], S: list[int]):
        crf.N, crf.A, crf.S = len(S), A, S
        S.append(len(A))

    def __len__(crf) -> int: return crf.N

    def __getitem__(crf, i: int) -> list[_T]:
        return crf.A[crf.S[i]:crf.S[i+1]]
    
    def get(crf, i: int, j: int) -> _T:
        return crf.A[crf.S[i]+j]
    
    def len(crf, i: int) -> int:
        return crf.S[i+1] - crf.S[i]

def roll(A: list, t: int):
    if t:=t%len(A): A[:t], A[t:] = A[-t:], A[:-t]
    return A

from array import array

def i8f(N: int, elm: int = 0):      return array('b', (elm,))*N  # signed char
def u8f(N: int, elm: int = 0):      return array('B', (elm,))*N  # unsigned char
def i16f(N: int, elm: int = 0):     return array('h', (elm,))*N  # signed short
def u16f(N: int, elm: int = 0):     return array('H', (elm,))*N  # unsigned short
def i32f(N: int, elm: int = 0):     return array('i', (elm,))*N  # signed int
def u32f(N: int, elm: int = 0):     return array('I', (elm,))*N  # unsigned int
def i64f(N: int, elm: int = 0):     return array('q', (elm,))*N  # signed long long
# def u64f(N: int, elm: int = 0):     return array('Q', (elm,))*N  # unsigned long long
def f32f(N: int, elm: float = 0.0): return array('f', (elm,))*N  # float
def f64f(N: int, elm: float = 0.0): return array('d', (elm,))*N  # double

def i8a(init = None):  return array('b') if init is None else array('b', init)  # signed char
def u8a(init = None):  return array('B') if init is None else array('B', init)  # unsigned char
def i16a(init = None): return array('h') if init is None else array('h', init)  # signed short
def u16a(init = None): return array('H') if init is None else array('H', init)  # unsigned short
def i32a(init = None): return array('i') if init is None else array('i', init)  # signed int
def u32a(init = None): return array('I') if init is None else array('I', init)  # unsigned int
def i64a(init = None): return array('q') if init is None else array('q', init)  # signed long long
# def u64a(init = None): return array('Q') if init is None else array('Q', init)  # unsigned long long
def f32a(init = None): return array('f') if init is None else array('f', init)  # float
def f64a(init = None): return array('d') if init is None else array('d', init)  # double

i8_max = (1 << 7)-1
u8_max = (1 << 8)-1
i16_max = (1 << 15)-1
u16_max = (1 << 16)-1
i32_max = (1 << 31)-1
u32_max = (1 << 32)-1
i64_max = (1 << 63)-1
u64_max = (1 << 64)-1

def elist(est_len: int) -> list: ...
try:
    from __pypy__ import newlist_hint
except:
    def newlist_hint(hint):
        return []
elist = newlist_hint
    

class PermGraph(FuncGraph):
    def inv(P):
        Pinv = [0]*P.N
        for i,p in enumerate(P):
            Pinv[p] = i
        return type(P)(Pinv)

def main():
    N, K = read(tuple[int,int])
    P = read(PermGraph[N,0])
    win = SlidingMinMax(maxlen=K)
    win.extend(P[:K])
    ans = 1 - (unchanged := len(win.minq) == K)
    for i in range(K,N):
        p = win.popleft()
        win.append(P[i])
        unchanged |= (is_sorted:=len(win.minq) == K)
        ans += not is_sorted and (p > win.min or P[i] < win.max)
        
    ans += unchanged
    write(ans)
    


def list_find(lst: list, value, start = 0, stop = sys.maxsize):
    try:
        return lst.index(value, start, stop)
    except:
        return -1
from typing import MutableSequence, SupportsIndex

class Deque(MutableSequence[_T]):
    def __init__(que, A = tuple(), *, maxlen=-1):
        super().__init__()
        data = [0]*maxlen
        que._sz = que._t = len(A)
        for i,a in enumerate(A): data[i] = a
        que._h, que.maxlen, que.data = 0, maxlen, data

    def __len__(que):
        return que._sz 
    
    def __contains__(que, x):
        if que._h >= que._t:
            return (list_find(que.data, x, 0, que._t) != -1
                or list_find(que.data, x, que._h, que.maxlen) != -1)
        else:
            return list_find(que.data, x, que._h, que._t) != -1
        
    def __getitem__(que, i: SupportsIndex) -> _T:
        assert -que._sz <= i < que._sz
        if i >= 0: return que.data[(que._h+i)%que.maxlen]
        else: return que.data[(que._t+i)%que.maxlen]
        
    def __setitem__(que, i: SupportsIndex, x):
        assert -que._sz <= i < que._sz
        if i >= 0: que.data[(que._h+i)%que.maxlen] = x
        else: que.data[(que._t+i)%que.maxlen] = x
    
    def head(que) -> _T: return que.data[que._h]

    def tail(que) -> _T: return que.data[(que._t-1)%que.maxlen]

    def __delitem__(que, i: SupportsIndex):
        raise NotImplemented
    
    def insert(que, i: SupportsIndex, x):
        raise NotImplemented
    
    def append(que, x):
        que.data[t := que._t] = x
        que._t = (t+1)%que.maxlen
        if que._sz == que.maxlen: que._h = que._t
        else: que._sz += 1

    def appendleft(que, x):
        que._h = (que._h-1)%que.maxlen
        que.data[que._h] = x
        if que._sz == que.maxlen: que._t = que._h
        else: que._sz += 1

    def pop(que) -> _T:
        assert que._sz, "Deque is empty"
        que._t = (que._t-1)%que.maxlen
        que._sz -= 1
        return que.data[que._t]
    
    def popleft(que) -> _T:
        assert que._sz, "Deque is empty"
        x = que.data[h := que._h]
        que._h = (h+1)%que.maxlen
        que._sz -= 1
        return x

class SlidingMinMax(Deque[_T]):
    def __init__(self, *, maxlen):
        super().__init__(maxlen=maxlen)
        self.minq = Deque(maxlen=maxlen)
        self.maxq = Deque(maxlen=maxlen)

    def append(self, x: _T) -> None:
        while self.minq and x < self.minq.tail(): self.minq.pop()
        self.minq.append(x)
        while self.maxq and self.maxq.tail() < x: self.maxq.pop()
        self.maxq.append(x)
        super().append(x)
    
    def appendleft(self, x: _T) -> None:
        raise NotImplemented
    
    def extend(self, iterable: Iterable) -> None:
        for x in iterable: self.append(x)

    def extendleft(self, iterable: Iterable) -> None:
        raise NotImplemented

    def popleft(self) -> _T:
        x = super().popleft()
        if x == self.minq.head(): self.minq.popleft()
        if x == self.maxq.head(): self.maxq.popleft()
        return x
    
    def pop(self) -> _T: raise NotImplemented

    @property
    def min(self) -> _T: return self.minq.head()

    @property
    def max(self) -> _T: return self.maxq.head()

from typing import Iterable, Type, Union, overload

@overload
def read() -> Iterable[int]: ...
@overload
def read(spec: int) -> list[int]: ...
@overload
def read(spec: Union[Type[_T],_T], char=False) -> _T: ...
def read(spec: Union[Type[_T],_T] = None, char=False):
    if not char and spec is None: return map(int, TokenStream.default.line())
    parser: _T = Parser.compile(spec)
    return parser(CharStream.default if char else TokenStream.default)

def write(*args, **kwargs):
    '''Prints the values to a stream, or to stdout_fast by default.'''
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", IOWrapper.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 __name__ == "__main__":
    main()
Back to top page