#1056176 (PyPy3) No.404 部分門松列

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX