結果

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

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

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

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

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

    # Process each i from 1 to n
    result = []
    for i in range(1, n + 1):
        pos = position[i]
        left = L[pos] + 1
        right = R[pos] - 1

        if left > pos or right < pos:
            result.append(0)
            continue

        a_i = A[i - 1]

        # Calculate count_e: left end is pos
        X_e = a_i + S[pos - 1]
        start_e = pos
        end_e = right
        count_e = 0
        if start_e <= end_e:
            r_e = bisect.bisect_right(S, X_e, start_e, end_e + 1) - 1
            r_e = min(r_e, end_e)
            if r_e >= start_e:
                count_e = r_e - start_e + 1

        # Calculate count_f: left end is in [left, pos-1]
        count_f = 0
        if left <= pos - 1:
            r_max = end_e
            for l in range(pos - 1, left - 1, -1):
                X = a_i + S[l - 1]
                while r_max >= pos and S[r_max] > X:
                    r_max -= 1
                if r_max >= pos:
                    count_f += r_max - pos + 1

        total = count_e + count_f
        result.append(total)

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

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