結果

問題 No.1425 Yet Another Cyclic Shifts Sorting
コンテスト
ユーザー sotanishy
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 WA * 1 TLE * 8 MLE * 27
権限があれば一括ダウンロードができます

ソースコード

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