結果

問題 No.2304 Distinct Elements
コンテスト
ユーザー detteiuu
提出日時 2026-08-03 23:22:05
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 256 ms / 3,000 ms
+ 115µs
コード長 2,413 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 654 ms
コンパイル使用メモリ 95,988 KB
実行使用メモリ 118,528 KB
最終ジャッジ日時 2026-08-03 23:22:21
合計ジャッジ時間 13,252 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from heapq import heappush, heappop

class SlopeTrick:
    def __init__(self):
        self.min_f = 0
        self.L = []
        self.R = []
        self.add_l = 0
        self.add_r = 0
    
    def push_R(self, a):
        heappush(self.R, a-self.add_r)
    
    def top_R(self):
        return self.R[0]+self.add_r if self.R else INF
    
    def pop_R(self):
        val = self.top_R()
        if self.R: heappop(self.R)
        return val
    
    def push_L(self, a):
        heappush(self.L, -(a-self.add_l))
    
    def top_L(self):
        return -self.L[0]+self.add_l if self.L else -INF
    
    def pop_L(self):
        val = self.top_L()
        if self.L: heappop(self.L)
        return val
    
    def size(self):
        return len(self.L)+len(self.R)
    
    def query(self):
        return self.top_L(), self.top_R(), self.min_f
    
    def add_all(self, a):
        self.min_f += a
    
    def add_x_minus_a(self, a):
        self.min_f += max(self.top_L()-a, 0)
        self.push_L(a)
        self.push_R(self.pop_L())

    def add_a_minus_x(self, a):
        self.min_f += max(a-self.top_R(), 0)
        self.push_R(a)
        self.push_L(self.pop_R())
    
    def add_abs(self, a):
        self.add_x_minus_a(a)
        self.add_a_minus_x(a)
    
    def clear_right(self):
        self.R = []

    def clear_left(self):
        self.L = []
    
    def shift2(self, a, b):
        self.add_l += a
        self.add_r += b
    
    def shift(self, a):
        self.shift2(a, a)
    
    def get(self, x):
        ret = self.min_f
        for l in self.L:
            n = -l+self.add_l
            ret += max(n-x, 0)
        for r in self.R:
            n = r+self.add_r
            ret += max(x-n, 0)
        return ret
    
    def merge(self, st):
        if self.size() < st.size():
            self.L, st.L = st.L, self.L
            self.R, st.R = st.R, self.R
            self.add_l, st.add_l = st.add_l, self.add_l
            self.add_r, st.add_r = st.add_r, self.add_r
            self.min_f, st.min_f = st.min_f, self.min_f
        while st.R:
            self.add_x_minus_a(st.pop_R())
        while st.L:
            self.add_a_minus_x(st.pop_L())
        self.min_f += st.min_f

INF = 1<<60

N = int(input())
A = sorted(map(int, input().split()))

for i in range(N):
    A[i] -= i

ST = SlopeTrick()
for a in A:
    ST.clear_right()
    ST.add_abs(a)

print(ST.query()[2])
0