結果

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

ソースコード

diff # 

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
    
    # Precompute nearest smaller to the left and right
    left = [-1] * N
    stack = []
    for i in range(N):
        while stack and P[stack[-1]] >= P[i]:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        else:
            left[i] = -1
        stack.append(i)
    
    right = [N] * N
    stack = []
    for i in range(N-1, -1, -1):
        while stack and P[stack[-1]] >= P[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        else:
            right[i] = N
        stack.append(i)
    
    # Compute prefix sum
    prefix_sum = [0] * (N + 1)
    for i in range(1, N+1):
        prefix_sum[i] = prefix_sum[i-1] + P[i-1]
    
    pos_map = {num: i for i, num in enumerate(P)}
    
    for i in range(1, N+1):
        pos = pos_map[i]
        L = left[pos]
        R = right[pos]
        window_start = L + 1
        window_end = R - 1
        if window_start > window_end:
            print(0)
            continue
        
        total = 0
        b_ptr = pos
        for a in range(window_start, pos + 1):
            target = prefix_sum[a] + A[i-1]
            while b_ptr <= window_end and prefix_sum[b_ptr + 1] <= target:
                b_ptr += 1
            max_b = b_ptr - 1
            if max_b < pos:
                continue
            count = max_b - pos + 1
            total += count
        print(total)

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