結果

問題 No.1079 まお
ユーザー maspymaspy
提出日時 2020-05-17 20:36:29
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,279 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 48,312 KB
最終ジャッジ日時 2024-04-09 22:11:04
合計ジャッジ時間 13,889 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 26 ms
17,564 KB
testcase_01 AC 25 ms
10,752 KB
testcase_02 WA -
testcase_03 AC 27 ms
10,624 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 1,411 ms
30,012 KB
testcase_13 AC 1,693 ms
30,816 KB
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

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