結果

問題 No.1526 Sum of Mex 2
ユーザー gew1fw
提出日時 2025-06-12 15:14:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,919 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 193,628 KB
最終ジャッジ日時 2025-06-12 15:14:58
合計ジャッジ時間 5,735 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    from bisect import bisect_left, bisect_right
    
    pos = defaultdict(list)
    for idx, num in enumerate(A):
        pos[num].append(idx)
    
    ans = 0
    
    for x in range(1, N+2):
        x_pos = pos.get(x, [])
        regions = []
        prev = -1
        for p in x_pos:
            if prev + 1 <= p - 1:
                regions.append((prev + 1, p - 1))
            prev = p
        if prev + 1 <= N - 1:
            regions.append((prev + 1, N - 1))
        
        total = 0
        required = set(range(1, x)) if x > 1 else set()
        if x == 1:
            for (s, e) in regions:
                length = e - s + 1
                total += length * (length + 1) // 2
        else:
            if not required:
                continue
            for (s, e) in regions:
                if s > e:
                    continue
                sub = A[s:e+1]
                freq = defaultdict(int)
                cnt = 0
                left = 0
                unique = 0
                current = 0
                for right in range(len(sub)):
                    num = sub[right]
                    if num in required:
                        freq[num] += 1
                        if freq[num] == 1:
                            unique += 1
                    while unique == len(required):
                        current += len(sub) - right
                        num_left = sub[left]
                        if num_left in required:
                            freq[num_left] -= 1
                            if freq[num_left] == 0:
                                unique -= 1
                        left += 1
                total += current
        ans += x * total
    print(ans)

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