結果

問題 No.2374 ASKT Subsequences
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:33:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 178 ms / 2,000 ms
コード長 1,674 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 113,480 KB
最終ジャッジ日時 2025-03-20 20:34:03
合計ジャッジ時間 3,547 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict

def count_asaktu_subsequences():
    N = int(input())
    A = list(map(int, input().split()))
    
    # Precompute suffix counts. suffix_counts[i][v] is the number of v's in A[i+1..N-1]
    suffix_counts = [defaultdict(int) for _ in range(N + 1)]  # suffix_counts[N] is empty
    current_counts = defaultdict(int)
    for i in reversed(range(N)):
        suffix_counts[i] = current_counts.copy()
        current_counts[A[i]] += 1
    
    total = 0
    
    for k in range(N):
        a_val = A[k] - 10
        # Collect all i <k with A[i] == a_val
        list_ik = [i for i in range(k) if A[i] == a_val]
        if not list_ik:
            continue
        
        # Collect all j <k with A[j] >= A[k] +1
        j_k_list = [j for j in range(k) if A[j] >= (A[k] + 1)]
        j_k_list.sort()
        m = len(j_k_list)
        if m == 0:
            continue
        
        # Precompute the counts_l for each j in j_k_list
        counts_l = []
        for j in j_k_list:
            b_j = A[j] + 1
            cnt = suffix_counts[k].get(b_j, 0)
            counts_l.append(cnt)
        
        # Compute prefix sums for counts_l
        prefix_sums = [0] * (m + 1)
        for i in range(m):
            prefix_sums[i + 1] = prefix_sums[i] + counts_l[i]
        
        # For each i in list_ik, find the valid j's and accumulate the counts
        for i in list_ik:
            # Find the first index in j_k_list where j > i
            idx = bisect.bisect_right(j_k_list, i)
            sum_count = prefix_sums[m] - prefix_sums[idx]
            total += sum_count
    
    print(total)

count_asaktu_subsequences()
0