結果

問題 No.404 部分門松列
ユーザー lam6er
提出日時 2025-03-20 20:58:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,015 bytes
コンパイル時間 717 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 76,984 KB
最終ジャッジ日時 2025-03-20 20:59:02
合計ジャッジ時間 6,358 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 9 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from bisect import bisect_left, bisect_right

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    a = list(map(int, input[idx:idx+N])); idx += N
    Q = int(input[idx]); idx +=1
    queries = []
    for _ in range(Q):
        L = int(input[idx])
        H = int(input[idx+1])
        queries.append( (L, H) )
        idx +=2
    
    # Precompute all possible triplets
    res = []
    for j in range(N):
        if j ==0 or j ==N-1:
            continue  # can't be middle
        # for j as middle element
        a_j = a[j]
        left = a[:j]
        right = a[j+1:]
        # Case 1: a_j is max, all a_i <a_j, a_k <a_j
        left_less = []
        for ai in left:
            if ai <a_j:
                left_less.append(ai)
        right_less = []
        for ak in right:
            if ak <a_j:
                right_less.append(ak)
        
        same_pairs =0
        cnt_left = {}
        for ai in left_less:
            cnt_left[ai] = cnt_left.get(ai,0) +1
        cnt_right = {}
        for ak in right_less:
            cnt_right[ak] = cnt_right.get(ak,0) +1
        for ai in cnt_left:
            if ai in cnt_right:
                same_pairs += cnt_left[ai] * cnt_right[ai]
        
        max_case = len(left_less) * len(right_less) - same_pairs
        
        # Case 2: a_j is min, all a_i > a_j, a_k > a_j
        left_greater = []
        for ai in left:
            if ai >a_j:
                left_greater.append(ai)
        right_greater = []
        for ak in right:
            if ak >a_j:
                right_greater.append(ak)
        
        same_pairs_min =0
        cnt_left_min = {}
        for ai in left_greater:
            cnt_left_min[ai] = cnt_left_min.get(ai,0) +1
        cnt_right_min = {}
        for ak in right_greater:
            cnt_right_min[ak] = cnt_right_min.get(ak,0) +1
        for ai in cnt_left_min:
            if ai in cnt_right_min:
                same_pairs_min += cnt_left_min[ai] * cnt_right_min[ai]
        
        min_case = len(left_greater) * len(right_greater) - same_pairs_min
        
        res.append( (a_j, max_case + min_case) )
    
    # Collect all j's contributions (including j=0 and j=N-1 with 0)
    contributions = []
    for j in range(N):
        if j < len(res):
            contributions.append( res[j] )
        else:
            contributions.append( (a[j], 0) )
    
    # Sort the contributions by a_j
    contributions_sorted = sorted(contributions, key=lambda x: x[0])
    a_sorted = [x[0] for x in contributions_sorted]
    prefix_sum = [0] * (len(contributions_sorted) +1)
    for i in range(len(contributions_sorted)):
        prefix_sum[i+1] = prefix_sum[i] + contributions_sorted[i][1]
    
    # Process each query
    for L, H in queries:
        left = bisect_left(a_sorted, L)
        right_idx = bisect_right(a_sorted, H)
        total = prefix_sum[right_idx] - prefix_sum[left]
        print(total)
    
if __name__ == "__main__":
    main()
0