Участник:StasFomin/Solutions/codechef/COEX06 — различия между версиями

Текущая версия на 20:22, 29 октября 2021

• Codechef/COEX06

def get_status(N, b):    
    state = 'start'
    cnt = 0
    status = []
    status.append([state, cnt])
    for i in range(1, N):
        if b[i] > b[i-1]:
            if state == 'increasing':
                cnt += 1
            else:
                state = 'increasing'
                cnt = 2
        else:
            if state == 'decreasing':
                cnt += 1
            else:
                state = 'decreasing'
                cnt = 2
 
        status.append([state, cnt])
 
    return status
 
 
T = int(input())
for _ in range(T):
    N, K = list(map(int, input().strip().split()))
    b = list(map(int, input().strip().split()))    # length  of  b  equals  N
 
    left_right_status = get_status(N, b)
    right_left_status = get_status(N, b[::-1])[::-1]
 
    for elem in right_left_status:
        if elem[0] == 'decreasing':
            elem[0] = 'increasing'
        elif elem[0] == 'increasing':
            elem[0] = 'decreasing'
 
 
    increasing = 0
    decreasing = 0
    for i in range(1, K-1):
        if left_right_status[i+1][0] != left_right_status[i][0]:
            state = left_right_status[i][0]
            cnt = left_right_status[i][1]
            if state == 'increasing':
                increasing += cnt * (cnt - 1) // 2
            elif state == 'decreasing':
                decreasing += cnt * (cnt - 1) // 2
 
    state = left_right_status[K-1][0]
    cnt = left_right_status[K-1][1]
    if state == 'increasing':
            increasing += cnt * (cnt - 1) // 2
    elif state == 'decreasing':
        decreasing += cnt * (cnt - 1) // 2
 
 
    increasing_list = []
    decreasing_list = []
    increasing_list.append(increasing)
    decreasing_list.append(decreasing)
 
    for i in range(N-K):
        increasing = increasing_list[-1]
        decreasing = decreasing_list[-1]    
 
        state = left_right_status[i+K][0]
        cnt = left_right_status[i+K][1]
        if state == 'increasing':
            increasing += min(cnt-1, K)
        elif state == 'decreasing':
            decreasing += min(cnt-1, K)
 
        state = right_left_status[i][0]
        cnt = right_left_status[i][1]
        if state == 'increasing':
            increasing -= min(cnt-1, K)
        elif state == 'decreasing':
            decreasing -= min(cnt-1, K)
 
        increasing_list.append(increasing)
        decreasing_list.append(decreasing)
 
 
    result = sum(increasing_list) - sum(decreasing_list)
    print(result)