Problem p02904 (python)

Fixed submission:
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = 0
l = [1] * (n - k + 1)
for i in range(k - 1):
    if p[i] > p[i + 1]:
        c += 1
if c == 0:
    l[0] = 0
for i in range(k - 1, n - 1):
    if p[i] > p[i + 1]:
        c += 1
    if p[i - k + 1] > p[i - k + 2]:
        c -= 1
    if c == 0:
        l[i - k + 2] = 0
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
    while qa and p[qa[-1]] > p[i]:
        qa.pop()
    while qb and p[qb[-1]] < p[i]:
        qb.pop()
    qa.append(i)
    qb.append(i)
    if qa[0] == i - k:
        qa.popleft()
    if qb[0] == i - k:
        qb.popleft()
    if i >= k - 1:
        a[i - k + 1] = p[qa[0]]
        b[i - k + 1] = p[qb[0]]
ans = l[0]
for i in range(n - k - 1):
    if (p[i] > a[i + 1] or b[i + 1] > p[i + k + 1]) and l[i + 1]:
        ans += 1
print(ans + 1 - min(l))

Buggy submission (verdict: Runtime Error):
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = 0
l = [1] * (n - k + 1)
for i in range(k - 1):
    if p[i] > p[i + 1]:
        c += 1
if c == 0:
    l[0] = 0
for i in range(k - 1, n - 1):
    if p[i] > p[i + 1]:
        c += 1
    if p[i - k + 1] > p[i - k + 2]:
        c -= 1
    if c == 0:
        l[i - k + 2] = 0
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
    while qa and p[qa[-1]] > p[i]:
        qa.pop()
    while qb and p[qb[-1]] < p[i]:
        qb.pop()
    qa.append(i)
    qb.append(i)
    if qa[0] == i - k:
        qa.popleft()
    if qb[0] == i - k:
        qb.popleft()
    a[i - k + 1] = p[qa[0]]
    b[i - k + 1] = p[qb[0]]
ans = 1
for i in range(n - k - 1):
    if p[i] > a[i + 1] or b[i + 1] > p[i + k + 1] and l[i]:
        ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
t = 0
res = 0
c = 0
for i in range(k - 1):
    if p[i] > p[i + 1]:
        c += 1
if c == 0:
    t = 1
    res += 1
for i in range(k - 1, n - 1):
    if p[i] > p[i + 1]:
        c += 1
    if p[i - k + 1] > p[i - k + 2]:
        c -= 1
    if c == 0:
        t = 1
        res += 1
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
    while qa and p[qa[-1]] > p[i]:
        qa.pop()
    while qb and p[qb[-1]] < p[i]:
        qb.pop()
    qa.append(i)
    qb.append(i)
    if qa[0] == i - k:
        qa.popleft()
    if qb[0] == i - k:
        qb.popleft()
    a[i - k + 1] = p[qa[0]]
    b[i - k + 1] = p[qb[0]]
exit(0)
ans = 1
for i in range(n - k - 1):
    if p[i] > a[i + 1] or b[i + 1] > p[i + k + 1]:
        ans += 1
print(ans + t - res)

Buggy submission (verdict: Runtime Error):
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
t = 0
res = 0
c = 0
for i in range(k - 1):
    if p[i] > p[i + 1]:
        c += 1
if c == 0:
    t = 1
    res += 1
for i in range(k - 1, n - 1):
    if p[i] > p[i + 1]:
        c += 1
    if p[i - k + 1] > p[i - k + 2]:
        c -= 1
    if c == 0:
        t = 1
        res += 1
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
    while qa and p[qa[-1]] > p[i]:
        qa.pop()
    while qb and p[qb[-1]] < p[i]:
        qb.pop()
    qa.append(i)
    qb.append(i)
    if qa[0] == i - k:
        qa.popleft()
    if qb[0] == i - k:
        qb.popleft()
    a[i - k + 1] = p[qa[0]]
    b[i - k + 1] = p[qb[0]]
ans = 1
for i in range(n - k - 1):
    if p[i] > a[i + 1] or b[i + 1] > p[i + k + 1]:
        ans += 1
print(ans + t - res)