Problem:


Score : 700 points

Problem Statement

Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).

Now, he will perform the following operation exactly once:

Choose K consecutive elements in P and sort them in ascending order.

Find the number of permutations that can be produced as P after the operation.

Constraints

2 \leq N \leq 200000

2 \leq K \leq N

0 \leq P_i \leq N-1

P_0,P_1,\cdots,P_{N-1} are all different.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_0 P_1 \cdots P_{N-1}

Output

Print the number of permutations that can be produced as P after the operation.

Sample Input 1

5 3
0 2 1 4 3

Sample Output 1

2

Two permutations can be produced as P after the operation: (0,1,2,4,3) and (0,2,1,3,4).

Sample Input 2

4 4
0 1 2 3

Sample Output 2

1

Sample Input 3

10 4
2 0 1 3 7 5 4 6 8 9

Sample Output 3

6



Sample input:
5 3
0 2 1 4 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
s=set([P[0]])
z=0
u = False
p=P[0]
for i in range(1,K):
    r=p
    p=P[i]
    if r < p:
        z+=1
    else:
        z=0
    s.add(p)
if z == K-1:
    u = True
c=1
for i in range(N-K):
    r=p
    p=P[K+i]
    q=P[i]
    if max(s) > p:
        c+=1
    elif min(s) < q:
        if z >= K-1:
            c += 1 if u == False else 0
            u = True
        else:
            c+=1
    if max(s) < p:
        if r < p:
            z+=1
        else:
            z=0
    s.remove(P[i])
    s.add(p)
print(c)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k = LI()
    p = LI()
    iq = []
    aq = []
    for i in range(k):
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])

    r = 1
    s = set()
    for i in range(k,n):
        t = p[i]
        u = p[i-k]
        heapq.heappush(iq,t)
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        heapq.heappush(aq,-t)
        if iq[0] != u or aq[0] != -t:
            r += 1
        s.add(u)

    c = 1
    rr = set()
    for i in range(1,n):
        if p[i-1] < p[i]:
            c += 1
        else:
            if c >= k:
                rr.add(i)
                if c > k and (i - c) > 0:
                    rr.add(i-c)
            c = 1
    if c >= k:
        rr.add(n-c)

    # print(rr)
    # print(r,len(rr),r-(len(rr)-1),c,k)

    return max(1, r - max(0, len(rr)-1))


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k = LI()
    p = LI()
    iq = []
    aq = []
    for i in range(k):
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])

    r = 1
    s = set()
    for i in range(k,n):
        t = p[i]
        u = p[i-k]
        heapq.heappush(iq,t)
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        heapq.heappush(aq,-t)
        if iq[0] != u or aq[0] != -t:
            r += 1
        s.add(u)

    c = 1
    rr = set()
    for i in range(1,n):
        if p[i-1] < p[i]:
            c += 1
        else:
            if c >= k:
                rr.add(i)
                if c > k and (i - c) > 0:
                    rr.add(i-c-k+2)
            c = 1
    if c >= k:
        rr.add(n-c-k+1)

    # print(rr)
    # print(r,len(rr),r-(len(rr)-1),c,k)

    return max(1, r - max(0, len(rr)-1))


print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque

N, K = map(int, input().split())
P = list(map(int, input().split()))

maxQ = deque([])
minQ = deque([])

for i in range(K):
    while maxQ:
        if P[maxQ[-1]] <= P[i]:
            maxQ.pop()
        else:
            break
    maxQ.append(i)
    if maxQ[0] == i - K:
        maxQ.popleft()
    while minQ:
        if P[minQ[-1]] >= P[i]:
            minQ.pop()
        else:
            break
    minQ.append(i)
    if minQ[0] == i - K:
        minQ.popleft()

ans = 1
for left in range(N - K):
    right = left + K
    if P[left] <= P[minQ[0]] and P[right] >= P[maxQ[-1]]:
        pass
    else:
        ans += 1

    while maxQ:
        if P[maxQ[-1]] <= P[right]:
            maxQ.pop()
        else:
            break
    maxQ.append(right)
    if maxQ[0] == right - K:
        maxQ.popleft()
    while minQ:
        if P[minQ[-1]] >= P[right]:
            minQ.pop()
        else:
            break
    minQ.append(right)
    if minQ[0] == right - K:
        minQ.popleft()

print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k = LI()
    p = LI()
    iq = []
    aq = []
    for i in range(k):
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])

    r = 1
    s = set()
    for i in range(k,n):
        t = p[i]
        u = p[i-k]
        heapq.heappush(iq,t)
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        heapq.heappush(aq,-t)
        if iq[0] != u or aq[0] != -t:
            r += 1
        s.add(u)

    rr = 0
    c = 1
    for i in range(1,n):
        if p[i-1] < p[i]:
            c += 1
        else:
            if c >= k:
                rr += 1
                if c > k and (i - c) > 0:
                    rr += 1
            c = 1
    if c >= k:
        rr += 1

    # print(r,rr,r-(rr-1),c,k)

    return max(1, r - max(0, rr-1))


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k = LI()
    p = LI()
    iq = []
    aq = []
    for i in range(k):
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])

    r = 1
    s = set()
    for i in range(k,n):
        t = p[i]
        u = p[i-k]
        heapq.heappush(iq,t)
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        heapq.heappush(aq,-t)
        if iq[0] != u or aq[0] != -t:
            r += 1
        s.add(u)

    rr = 0
    c = 1
    for i in range(1,n):
        if p[i-1] < p[i]:
            c += 1
        else:
            if c >= k:
                rr += 1
                if (i - c) > 0:
                    rr += 1
            c = 1
    if c >= k:
        rr += 1

    return max(1, r - max(0, rr-1))


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k = LI()
    p = LI()
    iq = []
    aq = []
    for i in range(k):
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])

    r = 1
    s = set()
    for i in range(k,n):
        t = p[i]
        u = p[i-k]
        heapq.heappush(iq,t)
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        heapq.heappush(aq,-t)
        if iq[0] != u or aq[0] != -t:
            r += 1
        s.add(u)

    rr = 0
    c = 1
    for i in range(1,n):
        if p[i-1] < p[i]:
            c += 1
        else:
            if c >= k:
                rr += 1
                if (i - c) > 1:
                    rr += 1
            c = 1
    if c >= k:
        rr += 1

    return max(1, r - max(0, rr-1))


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k = LI()
    p = LI()
    iq = []
    aq = []
    for i in range(k):
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])

    r = 1
    s = set()
    for i in range(k,n):
        t = p[i]
        u = p[i-k]
        heapq.heappush(iq,t)
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        heapq.heappush(aq,-t)
        if iq[0] != u or aq[0] != -t:
            r += 1
        s.add(u)

    rr = 0
    c = 1
    for i in range(1,n):
        if p[i-1] < p[i]:
            c += 1
        else:
            if c >= k:
                rr += 1
                if (i - c) > 1:
                    rr += 1
            c = 1
    if c >= k:
        rr += 1

    return r - max(0, rr-1)


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k = LI()
    p = LI()
    iq = []
    aq = []
    for i in range(k):
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])

    r = 1
    s = set()
    for i in range(k,n):
        t = p[i]
        u = p[i-k]
        heapq.heappush(iq,t)
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        heapq.heappush(aq,-t)
        if iq[0] != u or aq[0] != -t:
            r += 1
        s.add(u)

    rr = 0
    c = 1
    for i in range(1,n):
        if p[i-1] < p[i]:
            c += 1
            if c >= k:
                rr += 1
        else:
            c = 1

    return r - max(0, rr-1)


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k = LI()
    p = LI()
    iq = []
    aq = []
    for i in range(k):
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])

    r = 1
    s = set()
    for i in range(k,n):
        t = p[i]
        u = p[i-k]
        heapq.heappush(iq,t)
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        heapq.heappush(aq,-t)
        if iq[0] != u or aq[0] != -t:
            r += 1
        s.add(u)

    rr = 0
    c = 0
    for i in range(n):
        if p[i-1] < p[i]:
            c += 1
            if c >= k:
                rr += 1
        else:
            c = 1

    return r - max(0, rr-1)


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k = LI()
    p = LI()
    iq = []
    aq = []
    for i in range(k):
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])

    r = 1
    s = set()
    for i in range(k,n):
        t = p[i]
        u = p[i-k]
        heapq.heappush(iq,t)
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        if iq[0] != u or aq[0] < -t:
            r += 1
        heapq.heappush(aq,-t)
        s.add(u)

    rr = 0
    c = 0
    for i in range(1,n):
        if p[i-1] < p[i]:
            c += 1
            if c >= k:
                rr += 1
        else:
            c = 1

    return r - max(0, rr-1)


print(main())

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
n,k=map(int,input().split())
def insert_sort(arr,start):
    for i in range(start,start+k) :
        j = i - 1
        ele = arr[i]
        while arr[j] > ele and j >= 0:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = ele
    return arr

p=list(map(int,input().split()))
y= deepcopy(p)
m=[]


for r in range(n-k+1):
    m.append(insert_sort(y,r))
    y=deepcopy(p)

m=list(map(list, set(map(tuple, m))))
print(len(m))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k = LI()
    p = LI()
    iq = []
    aq = []
    for i in range(k):
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])

    r = 1
    s = set()
    for i in range(k,n):
        t = p[i]
        u = p[i-k]
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        if iq[0] != u or aq[0] < -t:
            r += 1
        # print(u,iq,t,aq)
        heapq.heappush(iq,t)
        heapq.heappush(aq,-t)
        s.add(t)

    return r


print(main())

Submission status: Wrong Answer

Solution code:
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        ans = 0
        q = queue.Queue()
        before = 0
        tmp = 0
        for i, v in enumerate(input().split()):
            if int(v) != i:
                q.put(True)
                tmp += 1
            else:
                q.put(False)
            if i >= K:
                if before == tmp !=0:
                    pass
                elif tmp > 0:
                    ans += 1
                before = tmp
                if q.get():
                    tmp -= 1

        print(max(1, ans))


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
xs = list(map(int, input().split()))
from collections import deque
def slide_max(k, l):
    rs, rrs = [], set()
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x < l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        if len(dq) == k:
            rrs.add(i+1-k)
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs,rrs

def slide_min(k, l):
    rs = []
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x > l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs

(maxs, ns), mins = slide_max(k, xs), slide_min(k, xs)
r = 1
for i, (s, x) in enumerate(zip(xs, xs[k:])):
    if (x != maxs[i+1] or s != mins[i]) and (i+1 not in ns): 
        r+=1
if (0 not in ns) and (len(ns) > 0):
    r += 1
print(r)

Submission status: Wrong Answer

Solution code:
from collections import deque
def slidemax(X, k):
    q = deque([])
    ret = []
    for i in range(len(X)):
        while q and q[-1][1] <= X[i]:
            q.pop()
        deque.append(q, (i+k, X[i]))
        if q[0][0] == i:
            deque.popleft(q)
        if i >= k-1:
            ret.append(q[0][1])
    return ret

def slidemin(X, k):
    q = deque([])
    ret = []
    for i in range(len(X)):
        while q and q[-1][1] >= X[i]:
            q.pop()
        deque.append(q, (i+k, X[i]))
        if q[0][0] == i:
            deque.popleft(q)
        if i >= k-1:
            ret.append(q[0][1])
    return ret

N, K = map(int, input().split())
A = [int(a) for a in input().split()]

a = 0
cnt = 0
for i in range(1, N):
    if A[i-1] > A[i]: a = i 
    if i >= K-1 and a <= i - K + 1: cnt += 1

MA = slidemax(A, K)
MI = slidemin(A, K)
ans = 1 - max(cnt-1, 0)
for i in range(K, N):
    if MI[i-K] != A[i-K] or MA[i-K+1] != A[i]:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
xs = list(map(int, input().split()))

from collections import deque
def slide_max(k, l):
    rs = []
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x < l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs

def slide_min(k, l):
    rs = []
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x > l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs

maxs, mins = slide_max(k, xs), slide_min(k, xs)
aa, bb = xs[:k], xs[k:]

b, nb, bx = aa[0], aa[1], aa[-1]
ba = None
c = 1
for a in aa:
    if ba == None:
        ba = a
        continue
    if a > ba:
        c += 1
    else:
        c = 1
    ba = a

rok = False
if c == k:
    rok = True

r = 1
for i, (s, x) in enumerate(zip(xs[1:], bb)):

    if x > bx:
        c = min(c+1, k)
    else:
        c = 1
    bx = x

    if c == k:
        if not rok:
            r += 1
        rok = True
        continue

    if x != maxs[i+1]: 
        r+=1
    elif s != mins[i]:
        r+=1

print(r)

Submission status: Wrong Answer

Solution code:
import heapq
n, k = map(int,input().split())
p = list(map(int,input().split()))
p_list = p
p_max = list(map(lambda x:x*(-1), p))
p_max_list = p_max
ans = 1
flag = 0
sort_count = [0 for _ in range(n)]
for i in range(n-1):   
    if p[i] < p[i+1]:
        if flag == 0:
            sort_count[i] += 1
            flag = 1
            start = i
        else:
            sort_count[start] += 1
            
for i, j in enumerate(sort_count):
    if j < k:
        sort_count[i] = 0
    else:
        sort_count[i] = 1
        

hp_min = p[1:k-1]
hp_max = p_max[1:k-1]
heapq.heapify(hp_min)
heapq.heapify(hp_max)

for i in range(n-k):
    heapq.heappush(hp_min, p[i+k-1])
    heapq.heappush(hp_max, p_max[i+k-1])
    while hp_min[0] in p[:i+1]:
        heapq.heappop(hp_min)
    else:
        if hp_min[0] < p[i]:
            ans += 1
        else:
            while hp_max[0] in p_max[:i+1]:
                heapq.heappop(hp_max)
            else:
                if hp_max[0] < p_max[i+k]:
                    ans += 1
print(ans-sum(sort_count))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = [int(i) for i in input().split()]
count = 0

for i in range(n):
    if i+k < n:
        if p[i] <= min(p[i:i+k-1]) and p[i+k] >= max(p[i+1:i+k]):
            count += 1
    else:
        break

print(n-k+1-count)