結果

問題 No.1496 不思議な数え上げ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:11:26
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,648 bytes
コンパイル時間 248 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 190,748 KB
最終ジャッジ日時 2025-06-12 16:11:36
合計ジャッジ時間 7,348 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    ptr = 0
    N = int(data[ptr])
    ptr +=1
    
    P = list(map(int, data[ptr:ptr+N]))
    ptr += N
    
    A = list(map(int, data[ptr:ptr+N]))
    ptr += N
    
    # Convert P to 0-based
    P = [x-1 for x in P]
    
    # Compute prefix sums
    prefix = [0]*(N+1)
    for i in range(N):
        prefix[i+1] = prefix[i] + (P[i] +1)  # since P is 0-based, elements 0..N-1 correspond to 1..N
    
    # Compute L: previous smaller element index for each j (0-based)
    L = [-1]*N
    stack = []
    for j in range(N):
        while stack and P[stack[-1]] >= P[j]:
            stack.pop()
        if stack:
            L[j] = stack[-1]
        else:
            L[j] = -1
        stack.append(j)
    
    # Compute R: next smaller or equal element index for each j (0-based)
    R = [N]*N
    stack = []
    for j in range(N-1, -1, -1):
        while stack and P[stack[-1]] > P[j]:
            stack.pop()
        if stack:
            R[j] = stack[-1]
        else:
            R[j] = N
        stack.append(j)
    
    # Collect j for each i
    from collections import defaultdict
    idx = defaultdict(list)
    for j in range(N):
        idx[P[j]].append(j)
    
    # Process each i
    result = [0]*N
    for i in range(N):
        current_i = i  # 0-based i (original i is i+1)
        a_list = idx.get(current_i, [])
        total = 0
        for j in a_list:
            a_start = L[j] + 1
            a_end = j
            if a_start > a_end:
                continue
            b_start = j
            b_end = R[j] -1
            if b_start > b_end:
                continue
            
            sum_max = prefix[b_end +1] - prefix[a_start]
            if sum_max <= A[current_i]:
                count_a = a_end - a_start + 1
                count_b = b_end - b_start + 1
                total += count_a * count_b
            else:
                # Use two-pointer approach
                i_ptr = a_end
                j_ptr = b_end
                current_count =0
                while i_ptr >= a_start:
                    target = prefix[i_ptr] + A[current_i]
                    while j_ptr >= b_start and prefix[j_ptr +1] > target:
                        j_ptr -=1
                    if j_ptr >= b_start:
                        current_count += (j_ptr - b_start +1)
                    i_ptr -=1
                total += current_count
        result[current_i] = total
    
    # Output the result for each i from 1 to N (original i is 1-based)
    for x in result:
        print(x)
    
if __name__ == '__main__':
    main()
0