結果

問題 No.1496 不思議な数え上げ
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:21:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,096 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 133,376 KB
最終ジャッジ日時 2025-04-15 21:27:18
合計ジャッジ時間 7,066 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

    # Position array for each value (1-based)
    pos = [0] * (N + 1)
    for i in range(N):
        val = P[i]
        pos[val] = i

    # Compute left_less and right_less using monotonic stack
    left_less = [-1] * N
    stack = []
    for j in range(N):
        while stack and P[stack[-1]] > P[j]:
            stack.pop()
        if stack:
            left_less[j] = stack[-1]
        else:
            left_less[j] = -1
        stack.append(j)

    right_less = [N] * N
    stack = []
    for j in range(N-1, -1, -1):
        while stack and P[stack[-1]] > P[j]:
            stack.pop()
        if stack:
            right_less[j] = stack[-1]
        else:
            right_less[j] = N
        stack.append(j)

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

    # Process each i from 1 to N
    ans = [0] * (N + 1)
    for i in range(1, N+1):
        j = pos[i]
        l = left_less[j] + 1
        r = right_less[j] - 1
        a_start = l
        a_end = j
        if a_start > a_end:
            ans[i] = 0
            continue

        target_i = A[i-1]
        total = 0
        current_k = j + 1  # initial b+1 is j+1
        max_k = r + 1

        for a in range(a_start, a_end + 1):
            target = S[a] + target_i
            # Move current_k as far right as possible
            while current_k <= max_k and current_k <= N and S[current_k] <= target:
                current_k += 1
            best_k = current_k - 1
            if best_k < j + 1:
                count = 0
            else:
                actual_k = min(best_k, max_k)
                count = actual_k - (j + 1) + 1
                if count < 0:
                    count = 0
            total += count
        ans[i] = total

    for i in range(1, N+1):
        print(ans[i])

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