結果

問題 No.2809 Sort Query
ユーザー navel_tosnavel_tos
提出日時 2024-07-13 00:38:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,445 ms / 2,000 ms
コード長 3,464 bytes
コンパイル時間 626 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 274,136 KB
最終ジャッジ日時 2024-07-13 00:39:36
合計ジャッジ時間 78,993 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,364 KB
testcase_01 AC 1,170 ms
270,256 KB
testcase_02 AC 1,315 ms
270,616 KB
testcase_03 AC 1,123 ms
270,012 KB
testcase_04 AC 1,069 ms
256,756 KB
testcase_05 AC 1,097 ms
271,464 KB
testcase_06 AC 935 ms
209,536 KB
testcase_07 AC 909 ms
210,348 KB
testcase_08 AC 972 ms
210,812 KB
testcase_09 AC 886 ms
209,212 KB
testcase_10 AC 899 ms
210,552 KB
testcase_11 AC 926 ms
267,824 KB
testcase_12 AC 933 ms
272,844 KB
testcase_13 AC 953 ms
266,332 KB
testcase_14 AC 986 ms
267,248 KB
testcase_15 AC 997 ms
268,660 KB
testcase_16 AC 953 ms
266,336 KB
testcase_17 AC 945 ms
266,748 KB
testcase_18 AC 939 ms
266,712 KB
testcase_19 AC 923 ms
267,396 KB
testcase_20 AC 959 ms
273,684 KB
testcase_21 AC 1,381 ms
273,036 KB
testcase_22 AC 1,441 ms
274,136 KB
testcase_23 AC 1,445 ms
273,676 KB
testcase_24 AC 1,411 ms
270,184 KB
testcase_25 AC 1,409 ms
272,500 KB
testcase_26 AC 1,246 ms
270,228 KB
testcase_27 AC 1,226 ms
268,728 KB
testcase_28 AC 1,232 ms
270,168 KB
testcase_29 AC 1,197 ms
269,548 KB
testcase_30 AC 1,221 ms
269,636 KB
testcase_31 AC 885 ms
263,088 KB
testcase_32 AC 884 ms
262,460 KB
testcase_33 AC 890 ms
262,120 KB
testcase_34 AC 854 ms
262,368 KB
testcase_35 AC 861 ms
262,288 KB
testcase_36 AC 949 ms
270,456 KB
testcase_37 AC 944 ms
270,856 KB
testcase_38 AC 920 ms
270,428 KB
testcase_39 AC 945 ms
270,528 KB
testcase_40 AC 977 ms
271,208 KB
testcase_41 AC 952 ms
260,296 KB
testcase_42 AC 969 ms
260,220 KB
testcase_43 AC 919 ms
260,032 KB
testcase_44 AC 944 ms
261,776 KB
testcase_45 AC 1,013 ms
259,624 KB
testcase_46 AC 910 ms
259,664 KB
testcase_47 AC 891 ms
260,480 KB
testcase_48 AC 885 ms
260,236 KB
testcase_49 AC 881 ms
259,928 KB
testcase_50 AC 889 ms
260,820 KB
testcase_51 AC 981 ms
261,484 KB
testcase_52 AC 800 ms
259,880 KB
testcase_53 AC 729 ms
260,464 KB
testcase_54 AC 722 ms
261,140 KB
testcase_55 AC 733 ms
259,876 KB
testcase_56 AC 940 ms
203,976 KB
testcase_57 AC 856 ms
168,644 KB
testcase_58 AC 764 ms
168,872 KB
testcase_59 AC 883 ms
193,248 KB
testcase_60 AC 678 ms
235,812 KB
testcase_61 AC 894 ms
262,980 KB
testcase_62 AC 791 ms
168,392 KB
testcase_63 AC 928 ms
211,408 KB
testcase_64 AC 1,032 ms
251,024 KB
testcase_65 AC 636 ms
197,996 KB
testcase_66 AC 41 ms
54,704 KB
testcase_67 AC 40 ms
54,100 KB
testcase_68 AC 41 ms
54,616 KB
testcase_69 AC 40 ms
53,284 KB
testcase_70 AC 39 ms
53,580 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder 2809 Sort Query

#Binary Indexed Tree
class BinaryIndexedTree:
    def __init__(self, N): self._N, self.bit = N, [0] * (N + 1)
    def build(self, A):  #O(N)で構築
        C = [0] * (self._N + 1)
        for i in range(self._N): C[i + 1] = C[i] + A[i]
        for e in range( self._N.bit_length() ):
            d = 1 << e
            for L in range(0, self._N + 1 - d, d << 1): self.bit[L + d] = C[L + d] - C[L]
    def add(self, i, x):  #A[i] += x
        i += 1
        while i <= self._N: self.bit[i] += x; i += i & - i
    def sum(self, i):  #sum(A[0, 1, ･･･ , i])
        ans, i = 0, i + 1
        while i > 0: ans += self.bit[i]; i -= i & - i
        return ans
    def fold(self, Lt, Rt):  #半開区間A[Lt: Rt)の和
        ans = 0
        while Lt != Rt:
            if Lt > Rt: ans -= self.bit[Lt]; Lt -= Lt & - Lt
            else:       ans += self.bit[Rt]; Rt -= Rt & - Rt
        return ans
    #down: Falseなら単調増加、Trueなら単調減少を仮定する。
    #sum(i)の作用値がX以上/以下となる、最小のiを返す
    def bisect(self, X, down = False):
        b = (self._N + 1).bit_length() - 1; i, d = 1 << b, 1 << (b - 1); cnt = 0
        for b in range(b, -1, -1):
            if i > self._N: i -= d; d >>= 1
            elif not down and cnt + self.bit[i] >= X: i -= d; d >>= 1
            elif     down and cnt + self.bit[i] <= X: i -= d; d >>= 1
            elif b == 0: return i
            else: cnt += self.bit[i]; i += d; d >>= 1
        return i - 1


#入力受取  座標圧縮
N, Q = map(int, input().split())
A = list(map(int, input().split()))
D = A[:]
query = [None] * Q
for q in range(Q):
    t, *k = map(int, input().split())
    if t == 1:
        k, x = k
        query[q] = (t, k - 1, x)
        D.append(x)
    if t == 2:
        query[q] = (t, 0, 0)
    if t == 3:
        k = k[0]
        query[q] = (t, k - 1, 0)
D.sort()
nD = []
for d in D:
    if len(nD) == 0 or nD[-1] != d:
        nD.append(d)
D = nD
E = {j: i for i, j in enumerate(D)}
n = len(E)
A = [E[i] for i in A]
ans = []
R = [-1] * Q
for q, (t, k, x) in enumerate(query):
    if t == 1:
        query[q] = (t, k, E[x])
    if t == 3:
        ans.append(-1)
        R[q] = len(ans) - 1

#ソートの影響を受けないものと、ソートの影響を受ける場合は何回目のソートか調べる
B = A[:]
S = set(range(N))
X = []
for q, (t, k, x) in enumerate(query):
    if t == 1:
        B[k] = x
        S.add(k)
    if t == 2:
        S.clear()
        X.append([])
    if t == 3:
        if k in S:
            ans[R[q]] = B[k]
        else:
            X[-1].append((R[q], k))

#X[ソート回数]: (ansのindex, ソート順でk個目)
BIT = BinaryIndexedTree(n)
B = [0] * n
for Ai in A:
    B[Ai] += 1
BIT.build(B)
cnt = -1
diff = dict()
for q, (t, k, x) in enumerate(query):
    if t == 1:
        if cnt == -1:
            BIT.add(A[k], -1)
            A[k] = x
            BIT.add(A[k], +1)
        else:
            diff[k] = x  #変更フォルダに保存
    if t == 2:
        #1. 変更を保存
        if cnt >= 0:
            diff2 = dict()
            for k in diff:
                diff2[k] = BIT.bisect(k + 1)
            for k in diff:
                BIT.add(diff[k], +1)
                BIT.add(diff2[k], -1)
        cnt += 1
        diff = dict()

        #2. クエリに回答
        for q, k in X[cnt]:
            ans[q] = BIT.bisect(k + 1)

for i in ans: print(D[i])
0