結果

問題 No.1285 ゴミ捨て
ユーザー uni_pythonuni_python
提出日時 2020-11-27 18:34:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 186 ms / 2,000 ms
コード長 4,949 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 87,156 KB
実行使用メモリ 79,968 KB
最終ジャッジ日時 2023-08-19 07:27:20
合計ジャッジ時間 4,517 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
71,108 KB
testcase_01 AC 63 ms
71,492 KB
testcase_02 AC 68 ms
71,332 KB
testcase_03 AC 70 ms
71,520 KB
testcase_04 AC 65 ms
71,308 KB
testcase_05 AC 64 ms
71,260 KB
testcase_06 AC 66 ms
71,468 KB
testcase_07 AC 186 ms
79,968 KB
testcase_08 AC 111 ms
78,988 KB
testcase_09 AC 140 ms
78,740 KB
testcase_10 AC 175 ms
79,212 KB
testcase_11 AC 163 ms
78,928 KB
testcase_12 AC 150 ms
79,456 KB
testcase_13 AC 152 ms
79,680 KB
testcase_14 AC 172 ms
79,180 KB
testcase_15 AC 160 ms
79,056 KB
testcase_16 AC 128 ms
78,176 KB
testcase_17 AC 121 ms
78,180 KB
testcase_18 AC 119 ms
78,488 KB
testcase_19 AC 134 ms
79,372 KB
testcase_20 AC 117 ms
78,452 KB
testcase_21 AC 125 ms
78,912 KB
testcase_22 AC 184 ms
79,780 KB
testcase_23 AC 180 ms
79,600 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