結果

問題 No.1496 不思議な数え上げ
ユーザー lam6er
提出日時 2025-03-20 20:37:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,037 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 139,164 KB
最終ジャッジ日時 2025-03-20 20:37:53
合計ジャッジ時間 8,501 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    P = list(map(int, sys.stdin.readline().split()))
    A = list(map(int, sys.stdin.readline().split()))

    pos_of_i = [0] * (N + 1)  # 1-based
    for idx, val in enumerate(P):
        pos_of_i[val] = idx

    # Find left boundaries
    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)

    # Find right boundaries
    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)

    # Prepare prefix sum array
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i+1] = prefix[i] + P[i]

    for i in range(1, N+1):
        ai = A[i-1]
        if ai < i:
            print(0)
            continue
        pos = pos_of_i[i]
        left_bound = left[pos]
        right_bound = right[pos]
        L_start = left_bound + 1
        L_end = pos
        R_start = pos
        R_end = right_bound - 1
        if L_start > L_end or R_start > R_end:
            print(0)
            continue
        total = 0
        r = R_end
        # Iterate l from L_end downto L_start (inclusive)
        for l in range(L_end, L_start - 1, -1):
            sum_left = prefix[pos + 1] - prefix[l]
            remaining = ai - sum_left
            if remaining < 0:
                continue
            # Now adjust r to find maximum valid r
            while r >= R_start and (prefix[r + 1] - prefix[pos + 1] > remaining):
                r -= 1
            if r < R_start:
                continue
            # Number of valid r is (r - R_start + 1)
            count = r - R_start + 1
            total += count
        print(total)

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