結果

問題 No.1496 不思議な数え上げ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:38:26
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,426 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 299,704 KB
最終ジャッジ日時 2025-06-12 16:38:37
合計ジャッジ時間 7,698 ms
ジャッジサーバーID
（参考情報） 		judge4 / 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
    
    pos = [0] * (N + 2)  # 1-based to 0-based index
    for j in range(N):
        pos[P[j]] = j
    
    # Compute L[i]: nearest smaller to the left
    L = [-1] * (N + 2)
    stack = []
    for j in range(N):
        current_val = P[j]
        while stack and P[stack[-1]] > current_val:
            stack.pop()
        if stack:
            L[current_val] = stack[-1]
        else:
            L[current_val] = -1
        stack.append(j)
    
    # Compute R[i]: nearest smaller to the right
    R = [N] * (N + 2)
    stack = []
    for j in range(N-1, -1, -1):
        current_val = P[j]
        while stack and P[stack[-1]] > current_val:
            stack.pop()
        if stack:
            R[current_val] = stack[-1]
        else:
            R[current_val] = N
        stack.append(j)
    
    ans = [0] * (N + 2)  # ans[1..N]
    
    for i in range(1, N+1):
        j = pos[i]
        left_bound = L[i] + 1
        right_bound = R[i] - 1
        if left_bound > j or j > right_bound:
            ans[i] = 0
            continue
        
        a_max_left = j - left_bound
        b_max_right = right_bound - j
        if a_max_left < 0 or b_max_right < 0:
            ans[i] = 0
            continue
        
        # Compute left_sums: sum from j-a to j (a ranges from 0 to a_max_left)
        left_sums = []
        current_sum = 0
        for a in range(a_max_left + 1):
            current_sum += P[j - a]
            left_sums.append(current_sum)
        
        # Compute right_sums: sum from j+1 to j+b (b ranges from 0 to b_max_right)
        right_sums = [0]
        current_sum = 0
        for b in range(1, b_max_right + 1):
            current_sum += P[j + b]
            right_sums.append(current_sum)
        
        a_i = A[i-1]
        total = 0
        p = len(right_sums) - 1  # start from the end of right_sums
        
        for s_left in left_sums:
            while p >= 0 and s_left + right_sums[p] > a_i:
                p -= 1
            if p >= 0:
                total += (p + 1)  # number of valid right_sums[0..p]
        
        ans[i] = total
    
    for i in range(1, N+1):
        print(ans[i])

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