結果
| 問題 | No.1425 Yet Another Cyclic Shifts Sorting |
| ユーザー |
 sotanishy
|
| 提出日時 | 2021-03-18 22:17:52 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,023 bytes |
| コンパイル時間 | 158 ms |
| コンパイル使用メモリ | 82,272 KB |
| 実行使用メモリ | 66,356 KB |
| 最終ジャッジ日時 | 2024-04-28 12:48:50 |
| 合計ジャッジ時間 | 4,228 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 37 ms
58,112 KB |
| testcase_01 | AC | 38 ms
52,480 KB |
| testcase_02 | AC | 34 ms
52,736 KB |
| testcase_03 | AC | 37 ms
53,120 KB |
| testcase_04 | AC | 35 ms
52,736 KB |
| testcase_05 | TLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
ソースコード
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)