結果

問題 No.1496 不思議な数え上げ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:39:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,781 bytes
コンパイル時間 407 ms
コンパイル使用メモリ 82,200 KB
実行使用メモリ 133,784 KB
最終ジャッジ日時 2025-06-12 16:40:01
合計ジャッジ時間 8,457 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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

    pos = [0] * (n + 2)  # 1-based
    for i in range(n):
        val = P[i]
        pos[val] = i

    # Compute L and R using monotonic stack
    L = [-1] * n
    stack = []
    for i in range(n):
        while stack and P[stack[-1]] >= P[i]:
            stack.pop()
        if stack:
            L[i] = stack[-1]
        else:
            L[i] = -1
        stack.append(i)

    R = [n] * n
    stack = []
    for i in range(n-1, -1, -1):
        while stack and P[stack[-1]] >= P[i]:
            stack.pop()
        if stack:
            R[i] = stack[-1]
        else:
            R[i] = n
        stack.append(i)

    # Compute prefix sums
    S = [0] * (n + 1)
    for i in range(n):
        S[i+1] = S[i] + P[i]

    result = []
    for i in range(1, n + 1):
        p = pos[i]
        left_start = L[p] + 1
        left_end = p
        if left_start > left_end:
            result.append(0)
            continue
        right_start = p + 1
        right_end = R[p]
        if right_start > right_end:
            result.append(0)
            continue

        ans = 0
        a_i = A[i-1]
        # Precompute the right part's start and end
        rs = right_start
        re = right_end
        # Iterate over all l in [left_start, left_end]
        for l in range(left_start, left_end + 1):
            target = S[l] + a_i
            cnt = bisect.bisect_right(S, target, rs, re + 1) - rs
            ans += cnt
        result.append(ans)

    print('\n'.join(map(str, result)))

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