結果
問題 | No.1558 Derby Live |
ユーザー | Kiri8128 |
提出日時 | 2021-06-25 21:44:29 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 489 ms / 2,000 ms |
コード長 | 3,363 bytes |
コンパイル時間 | 545 ms |
コンパイル使用メモリ | 87,204 KB |
実行使用メモリ | 107,940 KB |
最終ジャッジ日時 | 2023-09-07 14:25:25 |
合計ジャッジ時間 | 17,284 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 423 ms
87,672 KB |
testcase_01 | AC | 440 ms
107,940 KB |
testcase_02 | AC | 66 ms
71,056 KB |
testcase_03 | AC | 335 ms
89,484 KB |
testcase_04 | AC | 302 ms
86,620 KB |
testcase_05 | AC | 307 ms
85,964 KB |
testcase_06 | AC | 385 ms
96,804 KB |
testcase_07 | AC | 98 ms
77,916 KB |
testcase_08 | AC | 399 ms
94,440 KB |
testcase_09 | AC | 404 ms
96,188 KB |
testcase_10 | AC | 395 ms
99,056 KB |
testcase_11 | AC | 411 ms
100,320 KB |
testcase_12 | AC | 416 ms
97,296 KB |
testcase_13 | AC | 426 ms
99,740 KB |
testcase_14 | AC | 448 ms
100,476 KB |
testcase_15 | AC | 442 ms
100,688 KB |
testcase_16 | AC | 457 ms
102,248 KB |
testcase_17 | AC | 471 ms
102,164 KB |
testcase_18 | AC | 471 ms
104,736 KB |
testcase_19 | AC | 471 ms
105,068 KB |
testcase_20 | AC | 468 ms
104,064 KB |
testcase_21 | AC | 453 ms
102,692 KB |
testcase_22 | AC | 455 ms
104,960 KB |
testcase_23 | AC | 464 ms
106,384 KB |
testcase_24 | AC | 455 ms
103,468 KB |
testcase_25 | AC | 462 ms
105,292 KB |
testcase_26 | AC | 489 ms
105,064 KB |
testcase_27 | AC | 463 ms
103,996 KB |
testcase_28 | AC | 453 ms
104,460 KB |
testcase_29 | AC | 466 ms
105,488 KB |
testcase_30 | AC | 451 ms
103,732 KB |
testcase_31 | AC | 472 ms
104,344 KB |
testcase_32 | AC | 469 ms
104,432 KB |
testcase_33 | AC | 68 ms
71,296 KB |
testcase_34 | AC | 67 ms
71,520 KB |
ソースコード
class SegmentTree(): def __init__(self, init, unitX, f): self.f = f # (X, X) -> X self.unitX = unitX self.f = f if type(init) == int: self.n = init self.n = 1 << (self.n - 1).bit_length() self.X = [unitX] * (self.n * 2) else: self.n = len(init) self.n = 1 << (self.n - 1).bit_length() self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init)) for i in range(self.n-1, 0, -1): self.X[i] = self.f(self.X[i*2], self.X[i*2|1]) def update(self, i, x): i += self.n self.X[i] = x i >>= 1 while i: self.X[i] = self.f(self.X[i*2], self.X[i*2|1]) i >>= 1 def getvalue(self, i): return self.X[i + self.n] def getrange(self, l, r): l += self.n r += self.n al = self.unitX ar = self.unitX while l < r: if l & 1: al = self.f(al, self.X[l]) l += 1 if r & 1: r -= 1 ar = self.f(self.X[r], ar) l >>= 1 r >>= 1 return self.f(al, ar) # Find r s.t. calc(l, ..., r-1) = True and calc(l, ..., r) = False def max_right(self, l, z): if l >= self.n: return self.n l += self.n s = self.unitX while 1: while l % 2 == 0: l >>= 1 if not z(self.f(s, self.X[l])): while l < self.n: l *= 2 if z(self.f(s, self.X[l])): s = self.f(s, self.X[l]) l += 1 return l - self.n s = self.f(s, self.X[l]) l += 1 if l & -l == l: break return self.n # Find l s.t. calc(l, ..., r-1) = True and calc(l-1, ..., r-1) = False def min_left(self, r, z): if r <= 0: return 0 r += self.n s = self.unitX while 1: r -= 1 while r > 1 and r % 2: r >>= 1 if not z(self.f(self.X[r], s)): while r < self.n: r = r * 2 + 1 if z(self.f(self.X[r], s)): s = self.f(self.X[r], s) r -= 1 return r + 1 - self.n s = self.f(self.X[r], s) if r & -r == r: break return 0 def debug(self): print("debug") print([self.getvalue(i) for i in range(min(self.n, 20))]) def iv(A): iA = [0] * N for i, a in enumerate(A): iA[a] = i + 1 return iA def fun(A): re = 0 for i, a in enumerate(A): re += abs(i - a) return re import sys input = lambda: sys.stdin.readline().rstrip() N, M, Q = map(int, input().split()) f = lambda x, y: [y[xx] for xx in x] unit = [i for i in range(N)] st = SegmentTree(M, unit, f) for _ in range(Q): qq = [int(a) for a in input().split()] if qq[0] == 1: i = qq[1] - 1 A = [a - 1 for a in qq[2:]] st.update(i, A) elif qq[0] == 2: S = qq[1] re = st.getrange(0, S) print(*iv(re)) else: l, r = qq[1], qq[2] re = st.getrange(l - 1, r) print(fun(re))