結果

問題 No.1270 Range Arrange Query
ユーザー gew1fw
提出日時 2025-06-12 19:35:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,840 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 201,592 KB
最終ジャッジ日時 2025-06-12 19:35:47
合計ジャッジ時間 11,411 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 WA * 3 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

def main():
    sys.setrecursionlimit(1 << 25)
    N, Q = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    # Precompute prefix and suffix inversion counts
    prefix_inv = [0] * (N + 1)
    for i in range(1, N+1):
        cnt = 0
        for j in range(i-1, -1, -1):
            if a[j] > a[i-1]:
                cnt += 1
        prefix_inv[i] = prefix_inv[i-1] + cnt
    
    suffix_inv = [0] * (N + 2)
    for i in range(N, 0, -1):
        cnt = 0
        for j in range(i+1, N+1):
            if a[j-1] < a[i-1]:
                cnt += 1
        suffix_inv[i] = suffix_inv[i+1] + cnt
    
    for _ in range(Q):
        l, r = map(int, sys.stdin.readline().split())
        l -= 1  # converting to 0-based index
        r -= 1
        
        # Extract L and R
        L = a[:l]
        R = a[r+1:]
        
        # Compute inv(L) and inv(R)
        inv_L = prefix_inv[l]
        inv_R = suffix_inv[r+2]  # since suffix_inv is 1-based
        
        # Compute inv(L, R)
        sorted_L = sorted(L)
        sorted_R = sorted(R)
        
        i = 0
        count = 0
        for z in sorted_R:
            # Find the number of elements in sorted_L > z
            pos = bisect.bisect_right(sorted_L, z)
            count += len(sorted_L) - pos
        
        # Compute fixed = inv_L + inv_R + count
        fixed = inv_L + inv_R + count
        
        k = r - l + 1
        
        # Function to compute contributes(m)
        def contributes(m):
            # Number of elements in L > m
            cnt_L = len(sorted_L) - bisect.bisect_right(sorted_L, m)
            # Number of elements in R < m
            cnt_R = bisect.bisect_left(sorted_R, m)
            return cnt_L + cnt_R
        
        # Find m_opt via ternary search
        left = 1
        right = N
        m_opt = 1
        min_contrib = contributes(1)
        
        for _ in range(100):
            if left >= right:
                break
            m1 = left + (right - left) // 3
            m2 = right - (right - left) // 3
            c1 = contributes(m1)
            c2 = contributes(m2)
            if c1 < c2:
                right = m2
                if c1 < min_contrib:
                    min_contrib = c1
                    m_opt = m1
            else:
                left = m1
                if c2 < min_contrib:
                    min_contrib = c2
                    m_opt = m2
        
        # Check all possible m in a small range around m_opt
        for m in range(max(1, m_opt-5), min(N, m_opt+5)+1):
            c = contributes(m)
            if c < min_contrib:
                min_contrib = c
                m_opt = m
        
        S = k * min_contrib
        total = fixed + S
        print(total)

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