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:
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
p = list(map(int, input().split()))
 
cnt = 0
for i in range(n - k):
  first = [x - y for (x, y) in zip(p[i:i + k], sorted(p[i:i + k])) ]
  second = [a - b for (a, b) in zip(p[i + 1 : i + 1 + k], sorted(p[i + 1 : i + 1 + k])) ]
  if first != second:
    cnt += 1
    
if cnt == 0:
  print(1)
else:
  print(cnt)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
P = list(map(int,input().split()))
q1, q2 = [], []
if N == K:
    print(1)
    exit()
K += 1
res = 0
for i in range(N):
    while q1 and P[q1[-1]] <= P[i]:
        q1.pop()
    while q2 and P[q2[-1]] >= P[i]:
        q2.pop()
    q1.append(i)
    q2.append(i)
    if q1[0] == i - K:
        q1.pop(0)
    if q2[0] == i - K:
        q2.pop(0)
    if i >= K - 1:
        if P[i-K+1] == P[q1[0]] and P[i] == P[q2[0]]:
            continue
        else:
            res += 1
print(res)

Submission status: Wrong Answer

Solution code:
#B
#入力
N,K=map(int, input().split())
P=list(map(int,input().split()))
x=N-K+1
#処理
X=[P for i in range(x)]

#並び替えた順列を生成
for i in range(x):
    X[i]=X[i][:i]+sorted(X[i][i:i+K])+X[i][i+K:]

#重なりの判定
y=-1
while len(X)!=0:
    z=len(X)
    X.remove(X[0])

    y+=1
print(y)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
p = list(map(int, input().split()))
class SegTree:
  def segfunc(self, x, y):
    u = min(x[0], y[0])
    v = max(x[1], y[1])
    return (u, v) #ここ判定関数（ただし結合則があるもの）
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    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
p = [(x, x) for x in p]
seg = SegTree(N, (float("inf"), 0), p)
mini = [0] * (N - K + 1)
maxi = [0] * (N - K + 1)
for i in range(N - K + 1):
  temp = seg.query(i, i + K)
  mini[i] = temp[0]
  maxi[i] = temp[1]
#print(mini, maxi)
dcount = 0
alsorted = 0
temp = 0
for i in range(1, N - K + 1):
  if mini[i] != mini[i - 1] and maxi[i] != maxi[i - 1]:
    dcount += 1
for i in range(N - 1):
  if p[i][0] < p[i + 1][0]:
    temp += 1
  else: temp = 0
  if temp == K - 1:
    alsorted += 1
if alsorted == 0: alsorted = 1
print(N - K + 1 - dcount - alsorted + 1)

Submission status: Wrong Answer

Solution code:
class RangeMinimumQuery:
    def __init__(self, n, func=min, inf=float("inf")):
        self.n0 = 2**(n-1).bit_length()
        # 初期値
        self.op = func
        self.inf = inf
        self.data = [self.inf]*(2*self.n0-1)

    # [l, r)
    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.inf
        while l < r:
            if r&1:
                r -= 1
                res = self.op(res, self.data[r-1])
            if l&1:
                res = self.op(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i+1:
            i = ~-i//2
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

n,k = map(int, input().split())
p = list(map(int, input().split()))

RminQ = RangeMinimumQuery(n)
RmaxQ = RangeMinimumQuery(n, func=max, inf=0)

for i, pi in enumerate(p):
    RminQ.update(i, pi)
    RmaxQ.update(i, pi)

a = [1]
for i in range(n-1):
    if p[i] < p[i+1]:
        a.append(a[-1]+1)
    else:
        a.append(1)

uf = [-1]*(n-k+1)

def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx == ry:
        return False
    if uf[rx] > uf[ry]:
        rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

if max(a) == k:
    h = a.index(k)
    for i in range(n):
        if a[i] == k:
            unite(i-k+1, h-k+1)

for i in range(k, n):
    if p[i] > RmaxQ.query(i-k+1, i) and p[i-k] < RminQ.query(i-k+1, i):
        unite(i-k, i-k+1)

ans = sum(i<0 for i in uf)
print(ans)

Submission status: Wrong Answer

Solution code:
class RangeMinimumQuery:
    def __init__(self, n, func=min, inf=float("inf")):
        self.n0 = 2**(n-1).bit_length()
        # 初期値
        self.op = func
        self.inf = inf
        self.data = [self.inf]*(2*self.n0-1)

    # [l, r)
    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.inf
        while l < r:
            if r&1:
                r -= 1
                res = self.op(res, self.data[r-1])
            if l&1:
                res = self.op(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i+1:
            i = ~-i//2
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

n,k = map(int, input().split())
p = list(map(int, input().split()))

RminQ = RangeMinimumQuery(n)
RmaxQ = RangeMinimumQuery(n, func=max, inf=0)

for i, pi in enumerate(p):
    RminQ.update(i, pi)
    RmaxQ.update(i, pi)

a = [1]
for i in range(n-1):
    if p[i] < p[i+1]:
        a.append(a[-1]+1)
    else:
        a.append(1)

uf = [-1]*(n-k+1)

def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx == ry:
        return False
    if uf[rx] > uf[ry]:
        rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

if max(a) == k:
    h = a.index(k)
    for i in range(n):
        if a[i] == k:
            unite(i-k+1, h-k+1)

for i in range(k, n):
    if p[i] > RmaxQ.query(i-k+1, i) and p[i-k] < RminQ.query(i-k, i-1):
        unite(i-k, i-k+1)

ans = sum(i<0 for i in uf)
print(ans)

Submission status: Wrong Answer

Solution code:
class RangeMinimumQuery:
    def __init__(self, n, func=min, inf=float("inf")):
        self.n0 = 2**(n-1).bit_length()
        # 初期値
        self.op = func
        self.inf = inf
        self.data = [self.inf]*(2*self.n0-1)

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.inf
        while l < r:
            if r&1:
                r -= 1
                res = self.op(res, self.data[r-1])
            if l&1:
                res = self.op(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    # [l, r)
    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i+1:
            i = ~-i//2
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

n,k = map(int, input().split())
p = list(map(int, input().split()))

RminQ = RangeMinimumQuery(n)
RmaxQ = RangeMinimumQuery(n, func=max, inf=0)

for i, pi in enumerate(p):
    RminQ.update(i, pi)
    RmaxQ.update(i, pi)

a = [1]
for i in range(n-1):
    if p[i] < p[i+1]:
        a.append(a[-1]+1)
    else:
        a.append(1)

uf = [-1]*(n-k+1)

def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx == ry:
        return False
    if uf[rx] > uf[ry]:
        rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

if max(a) == k:
    h = a.index(k)
    for i in range(n):
        if a[i] == k:
            unite(i-k+1, h-k+1)

for i in range(k, n):
    if p[i] > RmaxQ.query(i-k+1, i) and p[i-k] < RminQ.query(i-k+1, i-1):
        unite(i-k, i-k+1)

ans = sum(i<0 for i in uf)
print(ans)

Submission status: Wrong Answer

Solution code:
class RangeMinimumQuery:
    def __init__(self, n, func=min, inf=float("inf")):
        self.n0 = 2**(n-1).bit_length()
        # 初期値
        self.op = func
        self.inf = inf
        self.data = [self.inf]*(2*self.n0-1)

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.inf
        while l < r:
            if r&1:
                r -= 1
                res = self.op(res, self.data[r-1])
            if l&1:
                res = self.op(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    # [l, r)
    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i+1:
            i = ~-i//2
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

n,k = map(int, input().split())
p = list(map(int, input().split()))

RminQ = RangeMinimumQuery(n)
RmaxQ = RangeMinimumQuery(n, func=max, inf=0)

for i, pi in enumerate(p):
    RminQ.update(i, pi)
    RmaxQ.update(i, pi)

a = [1]
for i in range(n-1):
    if p[i] < p[i+1]:
        a.append(a[-1]+1)
    else:
        a.append(1)

ans = n-k+1
h = a.index(max(a))
for i in range(k, n):
    if p[i] > RmaxQ.query(i-k+1, i) and p[i-k] < RminQ.query(i-k+1, i-1):
        ans -= 1
    elif a[i]==k and i != h:
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

n, k = map(int, input().split())
p = list(map(int, input().split()))

if n == k:
    print(1)
    exit()

ans = 1
s = sorted(p[:k])

for i in range(k, n):
    if p[i-k] != s[0] or p[i] < s[-1]:
        ans += 1
    s.pop(0)
    s.insert(bisect_left(s, p[i]), p[i])

print(ans)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
before_sort = False
M = max(p[:k])
m = min(p[:k])

before_sort_i = 0

for i in range(n - k + 1):
    if before_sort:
        if p[i + k - 1] < p[i + k - 2]:
            M = p[i + k - 2]
            num += 1
            before_sort = False 
        else:
            M = p[i + k - 1]
            before_sort_i += 1
        m = p[i]
        continue
    
    else:
        if before_sort_i + k <= i or i <= k:
            for j in range(k - 1):
                if p[i + j] > p[i + j +1]:
                    break
            else:
                if M == p[i - 1] or M < p[i + k - 2]:
                    M = max(p[i:i + k - 1])
                if m == p[i - 1] or m > p[i + k - 2]:
                    m = min(p[i:i + k - 1])

                if not ident:
                    ident = True
                    num += 1
                before_sort = True
                before_sort_i = i
                continue

            if i == 0:
                num += 1
                continue

            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])
                
            if p[i - 1] > m or p[i + k - 1] < M:
                num += 1  
        
        else:
            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])
                
            if p[i - 1] > m or p[i + k - 1] < M:
                num += 1
            if p[i + k - 1] <p[i + k - 2]:
                before_sort_i = i
    

print(num)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
so = False
M = max(p[:k])
m = min(p[:k])

print("{} {}".format(M,m))

for i in range(n - k + 1):
    if so:
        if p[i + k - 1] < p[i + k - 2]:
            M = p[i + k - 2]
            num += 1
            so = False
        else:
            M = p[i + k - 1]
        m = p[i]
        continue
    
    else:
        for j in range(k - 1):
            if p[i + j] > p[i + j +1]:
                break
        else:
            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])

            if not ident:
                ident = True
                num += 1
            so = True
            continue

        if i == 0:
            num += 1
            continue

        else:
            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])
    
            if p[i - 1] > m or p[i + k - 1] < M:
                num += 1       
    

print(num)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
so = False
M = max(p[:k])
m = min(p[:k])



for i in range(n - k + 1):
    if so:
        if p[i + k - 1] < p[i + k - 2]:
            num += 1
            so = False
        continue
    
    else:
        for j in range(k - 1):
            if p[i + j] > p[i + j +1]:
                break
        else:
            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])

            if not ident:
                ident = True
                num += 1
            so = True

            continue

        if i == 0:
            num += 1

            continue

        else:
            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])
    
            if p[i - 1] > m or p[i + k - 1] < M:
                num += 1
       
    

print(num)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
M = max(p[:k])
m = min(p[:k])


for i in range(n - k + 1):
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break

        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue
    else:
        if p[i - 1] > min(p[i:i + k - 1]) or p[i + k - 1] < max(p[i:i + k - 1]):
            num += 1      
    

print(num)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
M = max(p[:k])
m = min(p[:k])


for i in range(n - k + 1):
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break

        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue

        if p[i - 1] > min(p[i:i + k - 1]) or p[i + k - 1] < max(p[i:i + k - 1]):
            num += 1      
    

print(num)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
M = max(p[:k])
m = min(p[:k])


for i in range(n - k + 1):
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1

        continue

    if i == 0:
        num += 1

        continue

    else:
        if M == p[i - 1] or M < p[i + k - 2]:
            M = max(p[i:i + k - 1])
        if m == p[i - 1] or m > p[i + k - 2]:
            m = min(p[i:i + k - 1])
    
        if p[i - 1] > m or p[i + k - 1] < M:
            num += 1
     
    

print(num)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
M = max(p[:k])
m = min(p[:k])

for i in range(n - k + 1):
    if M == p[i]:
      M = max(p[i + 1:i + k])
    if m == p[i]:
      m = min(p[i + 1:i + k])
        
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue


    if p[i - 1] > m or p[i + k - 1] < M:
        num += 1
        break
    

print(num)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
M = max(p[:k])
m = min(p[:k])

for i in range(n - k + 1):
    if M == p[i]:
      M = max(p[i + 1:i + k])
    if m == p[i]:
      m = min(p[i + 1:i + k])
        
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue


    if p[i - 1] > M or p[i + k - 1] < m:
        num += 1
        break
    

print(num)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
M = max(p[:k])
m = min(p[:k])

for i in range(n - k + 1):
    if M == p[i]:
      M = max(p[i + 1:i + k])
    if m == p[i]:
      m = min(p[i + 1:i + k])
        
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue

    for j in range(1,k):
        if p[i - 1] > M or m < p[i + j - 1]:
            num += 1
            break
    

print(num)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
M = max(p[:k])
m = min(p[:k])

for i in range(n - k + 1):
    if M == p[i]:
      M = max(p[i:i + k])
    if m == p[i]:
      m = min(p[i:i + k])
        
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue

    for j in range(1,k):
        if p[i - 1] > M or m < p[i + j - 1]:
            num += 1
            break
    

print(num)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
import heapq

N, K = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]

ans = 0
Q_max = [-x for x in P[:K]]
Q_min = [x for x in P[:K]]
heapq.heapify(Q_min)
heapq.heapify(Q_max)
D = deque([x for x in P[:K]])
oc = 0
ordered_twice = False

for i in range(len(D) - 1):
    if D[i] <= D[i + 1]:
        oc += 1

for i in range(N - K + 1):
    if i == 0:
        ans += 1
        if oc == K - 1:
            ordered_twice = True
    else:
        D.popleft()
        D.append(P[i + K - 1])
        if P[i - 1] <= D[0]:
            oc -= 1
        if D[K - 2] <= D[K - 1]:
            oc += 1
        if oc == K - 1:
            if not ordered_twice:
                ordered_twice = True
                if P[i - 1] > Q_min[0] or D[K - 1] < -Q_max[0]:
                    ans += 1
        else:
            if P[i - 1] > Q_min[0] or D[K - 1] < -Q_max[0]:
                ans += 1
        if P[i - 1] == Q_min[0]:
            heapq.heappop(Q_min)
        if P[i - 1] == -Q_max[0]:
            heapq.heappop(Q_max)
        heapq.heappush(Q_min, D[K - 1])
        heapq.heappush(Q_max, -D[K - 1])

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
import heapq

N, K = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]

ans = 0
Q_max = [-x for x in P[:K]]
Q_min = [x for x in P[:K]]
heapq.heapify(Q_min)
heapq.heapify(Q_max)
D = deque([x for x in P[:K]])
oc = 0
ordered_twice = False

for i in range(len(D) - 1):
    if D[i] <= D[i + 1]:
        oc += 1

for i in range(N - K + 1):
    if i == 0:
        ans += 1
        if oc == K - 1:
            ordered_twice = True
    else:
        D.popleft()
        D.append(P[i + K - 1])
        if P[i - 1] <= D[0]:
            oc -= 1
        if D[K - 2] <= D[K - 1]:
            oc += 1
        if oc == K - 1:
            if not ordered_twice:
                ordered_twice = True
                if D[0] < Q_min[0] or D[K - 1] < -Q_max[0]:
                    ans += 1
        else:
            if D[0] < Q_min[0] or D[K - 1] < -Q_max[0]:
                ans += 1
        if P[i - 1] == Q_min[0]:
            heapq.heappop(Q_min)
        if P[i - 1] == -Q_max[0]:
            heapq.heappop(Q_max)
        heapq.heappush(Q_min, D[K - 1])
        heapq.heappush(Q_max, -D[K - 1])

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
INF = float('inf')
num = 2**(N-1).bit_length()
segmin = [INF] * num*2
segmax = [-INF] * num*2
for i in range(N):
    segmin[num + i - 1] = P[i]
    segmax[num + i - 1] = P[i]
for i in range(num-2, -1, -1):
    segmin[i] = min(segmin[2*i+1], segmin[2*i+2])
    segmax[i] = max(segmax[2*i+1], segmax[2*i+2])

def query(seg, f, boundary, p, q):
    p += num-1
    q += num-2
    res=boundary
    while q-p>1:
        if p&1 == 0:
            res = f(res,seg[p])
        if q&1 == 1:
            res = f(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = f(res,seg[p])
    else:
        res = f(f(res,seg[p]),seg[q])
    return res

ans = 1
for i in range(N-K):
    if not (P[i] < query(segmin, min, INF, i+1, i+K) and P[i+K] > query(segmax, max, -INF, i+1, i+K)):
        ans += 1

# 昇順にならんでいるケース
combo = 0
nord = 0
for i in range(1,N):
    if P[i] > P[i-1]:
        combo += 1
    else:
        combo = 0
    if combo >= K-1:
        nord += 1

print(ans - max(0, nord-1))

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy
N, K = map(int,input().split(' '))
P = np.array(list(map(int,input().split(' '))))
ans = []
for i in range(N-K+1):
  p = P
  q = copy.deepcopy(p)
  temp = np.sort(p[i:i+K])
  q[i:i+K] = temp
  if i == 0:
    t = copy.deepcopy(q)
    ans.append(t)
  else:
    for j in range(len(ans)):
      if not all(q == ans[j]):
        t = copy.deepcopy(q)
        ans.append(t)
        break
print(len(ans))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
P = [float('inf')]+list(map(int,input().split()))+[float('inf')]

A = [0]*N
B = [0]*(N+2)
hoge = 1
for i in range(1,N):
    if P[i] < P[i+1]:
        hoge += 1
    else:
        hoge = 1
    if hoge >= K:
        B[i] = 1
    
for i in range(1,N+1):
    A[P[i]] = i
minL,minR,maxL,maxR = [i-1 for i in range(N+2)],[i+1 for i in range(N+2)],[i-1 for i in range(N+2)],[i+1 for i in range(N+2)]
for i in range(N):
    m = A[i]
    x,y = maxL[m],maxR[m]
    maxL[y] = x
    maxR[x] = y
P[0],P[-1] = -1,-1

for i in range(N-1,-1,-1):
    m = A[i]
    x,y = minL[m],minR[m]
    minL[y] = x
    minR[x] = y
ans = 1
for i in range(1,N-K+1):
    # print(i)
    L,R = i,i+K
    # print(i,P[L],P[R],minR[L],maxL[R])
    if B[i] and (minR[L] <= R or maxL[R] >= L):
        # print(i)
        ans += 1
# print(minR[1:-1])
# print(maxL[1:-1])
if sum(B):
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy
N, K = map(int,input().split(' '))
P = np.array(list(map(int,input().split(' '))))
ans = []
for i in range(N-K):
  p = P
  q = copy.deepcopy(p)
  temp = np.sort(p[i:i+4])
  q[i:i+4] = temp
  if i == 0:
    t = copy.deepcopy(q)
    ans.append(t)
  else:
    for j in range(len(ans)):
      if not all(q == ans[j]):
        t = copy.deepcopy(q)
        ans.append(t)
        break
print(len(ans))

Submission status: Wrong Answer

Solution code:

N,K = map(int,input().split())
P = [float('inf')]+list(map(int,input().split()))+[float('inf')]

A = [0]*N
for i in range(1,N+1):
    A[P[i]] = i
minL,minR,maxL,maxR = [i-1 for i in range(N+2)],[i+1 for i in range(N+2)],[i-1 for i in range(N+2)],[i+1 for i in range(N+2)]
for i in range(N):
    m = A[i]
    x,y = maxL[m],maxR[m]
    maxL[y] = x
    maxR[x] = y
P[0],P[-1] = -1,-1

for i in range(N-1,-1,-1):
    m = A[i]
    x,y = minL[m],minR[m]
    minL[y] = x
    minR[x] = y
ans = 1
for i in range(2,N-K+1):
    L,R = i,i+K
    if minR[L] <= R or maxL[R] >= L:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]

c = 1
bf=False
for i in range(N-K+1):
    for j in range(1,K-1):
        for k in range(K-j):
            if ((i+j+k) <= (N-1)):
                if (A[i+k] > A[i+j+k]):
                    c = c + 1
                    #print (i,j,k)
                    bf=True
                    break
        if (bf):
            bf=False
            break

print(c)

Submission status: Wrong Answer

Solution code:
N,K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]

c = 0

for i in range(N-1):
    for j in range(K):
        if ((i+j) <= (N-1)):
            if (A[i] > A[i+j]):
                c = c + 1

print(c)

Submission status: Wrong Answer

Solution code:
N,K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
 
c = 0
 
for i in range(N-K):
    for j in range(K):
        if (A[i] > A[i+j]):
            c = c + 1
 
print(c)

Submission status: Wrong Answer

Solution code:
import math

#use an array for segment tree
#node i: left child 2i+1, right child 2i+2
def create_min_seg_tree(a):
	n = len(a)
	N = int(math.ceil(math.log(n,2)))
	tree = [10**9]*(2*2**N-1)
	for i in xrange(n):
		tree[2**N-1+i] = a[i]
	for i in xrange(2**N-2,-1,-1):
		tree[i] = min(tree[2*i+1], tree[2*i+2])		
	return tree

#ql, qr are query left and right
#sl, sr are segment left and right
def rmq(tree,node,ql,qr,sl,sr):
	if ql <= sl and sr <= qr:
		return tree[node]
	elif sr < ql or qr < sl:
		return 10**12
	else:
		mid = sl+(sr-sl)/2
		return min(rmq(tree,2*node+1,ql,qr,sl,mid),
					rmq(tree,2*node+2,ql,qr,mid+1,sr))

def create_max_seg_tree(a):
	n = len(a)
	N = int(math.ceil(math.log(n,2)))
	tree = [10**9]*(2*2**N-1)
	for i in xrange(n):
		tree[2**N-1+i] = a[i]
	for i in xrange(2**N-2,-1,-1):
		tree[i] = max(tree[2*i+1], tree[2*i+2])		
	return tree

#ql, qr are query left and right
#sl, sr are segment left and right
def rMq(tree,node,ql,qr,sl,sr):
	if ql <= sl and sr <= qr:
		return tree[node]
	elif sr < ql or qr < sl:
		return 10**12
	else:
		mid = sl+(sr-sl)/2
		return max(rmq(tree,2*node+1,ql,qr,sl,mid),
					rmq(tree,2*node+2,ql,qr,mid+1,sr))

n,k = map(int,raw_input().split())
a = map(int,raw_input().split())
mintree = create_min_seg_tree(a)
maxtree = create_max_seg_tree(a)
res = 1

for i in xrange(n-k-1):
	m = rmq(mintree,0,i+1,i+k,0,n-1)
	M = rMq(maxtree,0,i,i+k-1,0,n-1)
	if not (a[i] == m and a[i+k] == M):
		res += 1
print res

Submission status: Wrong Answer

Solution code:
inf = float('inf')

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

dp = [0] * (N+1)
dp[1] = 1
for i in range(1, N):
    if P[i-1] < P[i]:
        dp[i+1] += dp[i] + 1
    else:
        dp[i+1] = 1

class Max:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [-inf for _ in range(2*self.N)]
    
    def update(self, k, x):
        k += self.N-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = max([self.data[2*k+1], self.data[2*k+2]])
    
    # [l,r)
    def query(self, l, r):
        L = l + self.N
        R = r + self.N
        s = -inf
        while L < R:
            if R & 1:
                R -= 1
                s = max([s, self.data[R-1]])
            if L & 1:
                s = max([s, self. data[L-1]])
                L += 1
            L >>= 1; R >>= 1
        return s

class Min:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [inf for _ in range(2*self.N)]
    
    def update(self, k, x):
        k += self.N-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = min([self.data[2*k+1], self.data[2*k+2]])
        
    
    # [l,r)
    def query(self, l, r):
        L = l + self.N
        R = r + self.N
        s = inf
        while L < R:
            if R & 1:
                R -= 1
                s = min([s, self.data[R-1]])
            if L & 1:
                s = min([s, self. data[L-1]])
                L += 1
            L >>= 1; R >>= 1
        return s

Max = Max(N)
Min = Min(N)
for k in range(N):
    Max.update(k, P[k])
    Min.update(k, P[k])

ans = 1

check = [1] * (N-K+1) 
flag = 0
for i in range(N-K):
    if Min.query(i, i+K+2) == P[i] and Max.query(i, i+K+2) == P[i+K]:
        check[i+1] = 0

for i in range(N-K+1):
    if dp[i+K] >= K:
        check[i] = 0
        flag = 1

ans = sum(check) + flag
print(ans)

Submission status: Wrong Answer

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

n = 0
dp = [0] * (N+1)
for i in range(1,N):
    if P[i-1] < P[i]:
        dp[i] += dp[i-1] + 1
    else:
        if dp[i-1] >= K:
            n += 1
        dp[i] = 0

ans = 1
for l in range(1, N-K+1):
    if P[l-1] > P[l] or P[l+K-2] > P[l+K-1]:
        ans += 1

ans -= max(n-1, 0)
print(ans)

Submission status: Wrong Answer

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

# [l, r)
r = 1
n = 0
for l in range(N):
    while r < N and P[r-1] < P[r]:
        r += 1
    n += max(r - l - (K-1), 0)
    if r == l:
        r += 2

ans = 1
for l in range(1, N-K+1):
    if P[l-1] > P[l] or P[l+K-2] > P[l+K-1]:
        ans += 1

ans -= max(n-1, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
P = list(map(int,input().split()))
ans = 1
for l in range(1, N-K+1):
    if P[l-1] > P[l] or P[l+K-2] > P[l+K-1]:
        ans += 1
print(ans)