結果

問題 No.1425 Yet Another Cyclic Shifts Sorting
ユーザー sotanishysotanishy
提出日時 2021-03-18 22:17:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,023 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 895,872 KB
最終ジャッジ日時 2024-11-17 04:28:47
合計ジャッジ時間 66,571 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
57,984 KB
testcase_01 AC 40 ms
110,848 KB
testcase_02 AC 40 ms
57,856 KB
testcase_03 AC 39 ms
110,592 KB
testcase_04 AC 39 ms
57,984 KB
testcase_05 TLE -
testcase_06 TLE -
testcase_07 AC 40 ms
110,336 KB
testcase_08 TLE -
testcase_09 AC 41 ms
57,984 KB
testcase_10 AC 40 ms
57,856 KB
testcase_11 WA -
testcase_12 AC 41 ms
57,472 KB
testcase_13 AC 40 ms
393,472 KB
testcase_14 MLE -
testcase_15 MLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 AC 39 ms
52,736 KB
testcase_19 AC 40 ms
52,736 KB
testcase_20 AC 39 ms
52,736 KB
testcase_21 AC 40 ms
52,736 KB
testcase_22 MLE -
testcase_23 MLE -
testcase_24 MLE -
testcase_25 MLE -
testcase_26 MLE -
testcase_27 MLE -
testcase_28 MLE -
testcase_29 MLE -
testcase_30 MLE -
testcase_31 MLE -
testcase_32 MLE -
testcase_33 AC 574 ms
458,480 KB
testcase_34 MLE -
testcase_35 MLE -
testcase_36 MLE -
testcase_37 MLE -
testcase_38 MLE -
testcase_39 TLE -
testcase_40 MLE -
testcase_41 MLE -
testcase_42 MLE -
testcase_43 TLE -
testcase_44 MLE -
testcase_45 MLE -
testcase_46 MLE -
testcase_47 MLE -
testcase_48 MLE -
testcase_49 MLE -
testcase_50 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left
import sys
input = sys.stdin.readline

class FenwickTree:
    def __init__(self, size):
        self.data = [0] * (size + 1)
        self.size = size

    # i is exclusive
    def prefix_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

    def lower_bound(self, x):
        if x <= 0:
            return 0
        k = 1
        while k * 2 <= self.size:
            k *= 2
        i = 0
        while k > 0:
            if i + k <= self.size and self.data[i + k] < x:
                x -= self.data[i + k]
                i += k
            k //= 2
        return i + 1

class FenwickTreeSet:
    def __init__(self, max_val):
        self.max_val = max_val
        self.fw = FenwickTree(max_val + 1)

    def add(self, x):
        self.fw.add(x, 1)

    def remove(self, x):
        self.fw.add(x, -1)

    def pred(self, x):
        return self.fw.lower_bound(self.fw.prefix_sum(x)) - 1

    def succ(self, x):
        return self.fw.lower_bound(self.fw.prefix_sum(x) + 1) - 1

    def size(self):
        return self.fw.prefix_sum(self.max_val + 1)

class Compress:
    def __init__(self, vs):
        self.xs = list(set(vs))
        self.xs.sort()

    def compress(self, x):
        return bisect_left(self.xs, x)

    def decompress(self, i):
        return self.xs[i]

N = int(input())
A = list(map(int, input().split()))
comp = Compress(A)
A = [comp.compress(x) for x in A]
prv = [N - 1] + list(range(N - 1))
nxt = list(range(1, N)) + [0]
idx = [FenwickTreeSet(N - 1) for _ in range(N)]
for i, x in enumerate(A):
    idx[x].add(i)
i = N - 1
ans = 0
for x in sorted(A, reverse=True):
    if A[i] != x:
        i = idx[x].pred(i)
        if i == -1:
            idx[x].pred(N)
        ans += 1
    nxt[prv[i]] = nxt[i]
    prv[nxt[i]] = prv[i]
    idx[x].remove(i)
    i = prv[i]
print(ans)
0