結果

問題 No.1079 まお
ユーザー maspy
提出日時 2020-05-17 20:36:29
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,279 bytes
コンパイル時間 500 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 51,236 KB
最終ジャッジ日時 2024-10-01 22:44:12
合計ジャッジ時間 14,169 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 WA * 9 TLE * 4 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K, *A = map(int, read().split())

def solve(L, R):
    INF = 10**9 + 10
    # 半開区間[L,R)
    if R - L == 1:
        return A[L] * 2 == K
    M = (L + R) // 2
    ret = solve(L, M) + solve(M, R)

    # あとはM-1, Mを含むような解を求める。
    def compute(nums):
        min_value = 1 << 32
        min_cnt = 1
        for i, x in enumerate(nums, 1):
            if x == min_value:
                min_cnt += 1
            elif x < min_value:
                min_value = x
                min_cnt = 1
            if min_cnt == 1:
                yield i, x, min_value

    num_0 = defaultdict(int)
    sum_0 = defaultdict(int)
    num_1 = defaultdict(int)
    sum_1 = defaultdict(int)
    for i, x, min_value in compute(reversed(A[L:M])):
        num_0[x] += 1
        sum_0[x] += i
        key = (x << 32) + min_value
        num_1[key] += 1
        sum_1[key] += i

    for i, x, min_value in compute(A[M:R]):
        ret += i * num_0[K - x]
        ret += sum_0[K - x]
        key = (K - x << 32) + min_value
        ret -= i * num_1[key]
        ret -= sum_1[key]
    return ret

print(solve(0, N))
0