結果

問題 No.1285 ゴミ捨て
ユーザー uni_pythonuni_python
提出日時 2020-11-27 18:34:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 171 ms / 2,000 ms
コード長 4,949 bytes
コンパイル時間 135 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 78,336 KB
最終ジャッジ日時 2024-11-28 21:58:22
合計ジャッジ時間 3,426 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
53,120 KB
testcase_01 AC 35 ms
53,120 KB
testcase_02 AC 34 ms
52,992 KB
testcase_03 AC 34 ms
52,992 KB
testcase_04 AC 33 ms
52,864 KB
testcase_05 AC 33 ms
53,248 KB
testcase_06 AC 35 ms
53,120 KB
testcase_07 AC 164 ms
78,208 KB
testcase_08 AC 94 ms
77,184 KB
testcase_09 AC 119 ms
76,928 KB
testcase_10 AC 152 ms
77,696 KB
testcase_11 AC 146 ms
77,440 KB
testcase_12 AC 132 ms
77,184 KB
testcase_13 AC 130 ms
77,228 KB
testcase_14 AC 165 ms
78,080 KB
testcase_15 AC 137 ms
78,080 KB
testcase_16 AC 100 ms
77,056 KB
testcase_17 AC 100 ms
76,800 KB
testcase_18 AC 100 ms
76,928 KB
testcase_19 AC 116 ms
77,056 KB
testcase_20 AC 105 ms
76,928 KB
testcase_21 AC 115 ms
77,240 KB
testcase_22 AC 171 ms
77,952 KB
testcase_23 AC 163 ms
78,336 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input=sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


##############################
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる

    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき

        self.cnt=0#要素数を持っておくか
        inf = float("inf")
        self.square = square
        if values is None:
            self.rand_y = seed
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y ^= (y & 0x7ffff) << 13
                y ^= y >> 17
                y ^= (y & 0x7ffffff) << 5
                if y % square == 0:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer1.append(inf)
            layer0.append(l0)
            self.rand_y = y

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        # xorshift
        y = self.rand_y
        y ^= (y & 0x7ffff) << 13
        y ^= y >> 17
        y ^= (y & 0x7ffffff) << 5
        self.rand_y = y

        if y % self.square == 0:
            layer1, layer0 = self.layer1, self.layer0
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(self.layer1, x)
            insort_right(self.layer0[idx1], x)

        self.cnt+=1#追加

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        # x が存在しない場合、x 以上の最小の要素が削除される
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del self.layer1[idx1]
            self.layer0[idx1] += self.layer0.pop(idx1+1)
        else:
            del layer0_idx1[idx0]

        self.cnt-=1

    def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        idx1 = bisect_right(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        #x未満のものがない場合，infが返るかも！！！  
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return self.layer1[idx1-1]
        return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め、使うなら square パラメータを大きめにするべき
        self.cnt-=1
        layer0 = self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0.pop(i+1)
            return self.layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)


    def all(self):
        print(self.layer1)
        print(self.layer0)

    def len(self):
        return self.cnt

##############################



N=I()
inf=10**10
ssl = SquareSkipList(square=4000)
ssl.add(inf)
A=[0]*N
for i in range(N):
    A[i]=I()
    
A.sort(reverse=True)

for i in range(N):
    a=A[i]
    h=ssl.search_higher_equal(a+2)
    if h!=inf:
        ssl.remove(h)
        ssl.add(a)
    else:
        ssl.add(a)
    
    

    
print(ssl.len()-1)
0