結果

問題 No.1496 不思議な数え上げ
ユーザー lam6er
提出日時 2025-04-15 21:23:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,143 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 148,436 KB
最終ジャッジ日時 2025-04-15 21:29:11
合計ジャッジ時間 8,873 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    # Convert to 1-based indexing
    P = [0] + P
    A = [0] + A
    
    pos = [0] * (n + 1)
    for i in range(1, n + 1):
        pos[P[i]] = i
    
    # Compute L and R using monotonic stack
    L = [0] * (n + 2)
    stack = []
    for i in range(1, n + 1):
        while stack and P[stack[-1]] >= P[i]:
            stack.pop()
        L[i] = stack[-1] if stack else 0
        stack.append(i)
    
    R = [n + 1] * (n + 2)
    stack = []
    for i in range(n, 0, -1):
        while stack and P[stack[-1]] >= P[i]:
            stack.pop()
        R[i] = stack[-1] if stack else n + 1
        stack.append(i)
    
    # Compute prefix sums
    S = [0] * (n + 1)
    for i in range(1, n + 1):
        S[i] = S[i - 1] + P[i]
    
    ans = [0] * (n + 1)
    
    for i in range(1, n + 1):
        ai = A[i]
        if ai < i:
            ans[i] = 0
            continue
        j = pos[i]
        # Compute left_sum
        L_j = L[j]
        left_max = j - (L_j + 1)
        left_sum = []
        for d_left in range(left_max + 1):
            l = j - d_left
            sum_val = S[j] - S[l - 1]
            left_sum.append(sum_val)
        # Compute right_sum
        R_j = R[j]
        right_max = (R_j - 1) - j
        right_max = max(0, right_max)
        right_sum = [0]  # d_right=0
        for d_right in range(1, right_max + 1):
            r = j + d_right
            sum_val = S[r] - S[j]
            right_sum.append(sum_val)
        # Sort left_sum
        left_sum.sort()
        # Count pairs
        total = 0
        for dr in range(len(right_sum)):
            current_right = right_sum[dr]
            X = ai - current_right
            if X < 0:
                continue
            cnt = bisect.bisect_right(left_sum, X)
            total += cnt
        ans[i] = total
    
    for i in range(1, n + 1):
        print(ans[i])

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