結果

問題 No.1496 不思議な数え上げ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:18:20
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,707 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 81,796 KB
実行使用メモリ 152,964 KB
最終ジャッジ日時 2025-06-12 21:18:38
合計ジャッジ時間 9,470 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

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

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

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

    S = [0] * (N + 1)
    for i in range(1, N+1):
        S[i] = S[i-1] + P[i-1]

    result = [0] * (N + 1)
    for i in range(1, N+1):
        m = pos[i]
        L = left[m] + 1
        R = right[m] - 1
        if L > m or R < m:
            result[i] = 0
            continue
        ans = 0
        for l in range(L, m + 1):
            target = S[l-1] + A[i-1]
            low = m
            high = R
            r_max = m - 1
            while low <= high:
                mid = (low + high) // 2
                if S[mid] <= target:
                    r_max = mid
                    low = mid + 1
                else:
                    high = mid - 1
            if r_max >= m:
                ans += r_max - m + 1
        result[i] = ans

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

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