結果

問題 No.1496 不思議な数え上げ
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:46:36
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,007 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,720 KB
実行使用メモリ 133,712 KB
最終ジャッジ日時 2025-03-31 17:47:36
合計ジャッジ時間 7,293 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    P = list(map(int, input[ptr:ptr+n]))
    ptr += n
    A = list(map(int, input[ptr:ptr+n]))
    ptr += n

    pos = [0] * (n + 2)  # 1-based to 0-based index
    for idx, val in enumerate(P):
        pos[val] = idx

    # Compute L[j] (previous smaller element's index)
    L = [-1] * n
    stack = []
    for j in range(n):
        while stack and P[stack[-1]] > P[j]:
            stack.pop()
        if stack:
            L[j] = stack[-1]
        else:
            L[j] = -1
        stack.append(j)

    # Compute R[j] (next smaller element's index)
    R = [n] * n
    stack = []
    for j in reversed(range(n)):
        while stack and P[stack[-1]] > P[j]:
            stack.pop()
        if stack:
            R[j] = stack[-1]
        else:
            R[j] = n
        stack.append(j)

    # Compute prefix sum array
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + P[i]

    result = [0] * (n + 1)  # 1-based for result[1..n]

    for i in range(1, n + 1):
        j = pos[i]
        left = L[j] + 1
        right_end = R[j] - 1
        if left > j or j > right_end:
            result[i] = 0
            continue

        start_l = left
        end_l = j
        start_r_plus1 = j + 1
        end_r_plus1 = right_end + 1

        Ai = A[i - 1]

        total = 0
        prev_found = start_r_plus1

        for l in range(start_l, end_l + 1):
            X = prefix_sum[l] + Ai

            found = bisect.bisect_right(prefix_sum, X, prev_found, end_r_plus1 + 1)
            max_r_plus1 = found - 1

            if max_r_plus1 >= start_r_plus1:
                cnt = max_r_plus1 - start_r_plus1 + 1
            else:
                cnt = 0

            total += cnt
            prev_found = found

        result[i] = total

    for i in range(1, n + 1):
        print(result[i])

if __name__ == "__main__":
    main()
0