結果
問題 | No.1471 Sort Queries |
ユーザー | toyuzuko |
提出日時 | 2021-04-17 19:06:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 4,187 bytes |
コンパイル時間 | 657 ms |
コンパイル使用メモリ | 87,172 KB |
実行使用メモリ | 80,584 KB |
最終ジャッジ日時 | 2023-09-17 04:37:45 |
合計ジャッジ時間 | 7,242 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 65 ms
71,540 KB |
testcase_01 | AC | 64 ms
71,476 KB |
testcase_02 | AC | 65 ms
71,520 KB |
testcase_03 | AC | 86 ms
76,936 KB |
testcase_04 | AC | 80 ms
76,824 KB |
testcase_05 | AC | 79 ms
76,824 KB |
testcase_06 | AC | 66 ms
71,416 KB |
testcase_07 | AC | 85 ms
76,684 KB |
testcase_08 | AC | 80 ms
76,900 KB |
testcase_09 | AC | 76 ms
77,044 KB |
testcase_10 | AC | 71 ms
76,124 KB |
testcase_11 | AC | 77 ms
76,784 KB |
testcase_12 | AC | 84 ms
77,372 KB |
testcase_13 | AC | 129 ms
77,972 KB |
testcase_14 | AC | 129 ms
78,320 KB |
testcase_15 | AC | 133 ms
78,536 KB |
testcase_16 | AC | 131 ms
80,584 KB |
testcase_17 | AC | 129 ms
78,716 KB |
testcase_18 | AC | 121 ms
78,280 KB |
testcase_19 | AC | 126 ms
79,908 KB |
testcase_20 | AC | 122 ms
78,244 KB |
testcase_21 | AC | 125 ms
78,308 KB |
testcase_22 | AC | 127 ms
78,356 KB |
testcase_23 | AC | 141 ms
79,328 KB |
testcase_24 | AC | 140 ms
79,340 KB |
testcase_25 | AC | 141 ms
79,248 KB |
testcase_26 | AC | 131 ms
78,268 KB |
testcase_27 | AC | 134 ms
79,700 KB |
testcase_28 | AC | 139 ms
80,444 KB |
testcase_29 | AC | 133 ms
78,436 KB |
testcase_30 | AC | 134 ms
78,660 KB |
testcase_31 | AC | 142 ms
78,648 KB |
testcase_32 | AC | 131 ms
78,872 KB |
testcase_33 | AC | 136 ms
80,008 KB |
testcase_34 | AC | 135 ms
79,836 KB |
testcase_35 | AC | 134 ms
79,976 KB |
testcase_36 | AC | 136 ms
79,804 KB |
testcase_37 | AC | 144 ms
79,164 KB |
testcase_38 | AC | 144 ms
80,316 KB |
testcase_39 | AC | 150 ms
79,760 KB |
ソースコード
class FullyIndexableDictionary(): def __init__(self, size): self.size = size self.block = (size + 31) >> 5 self.bit = [0] * self.block self.sum = [0] * self.block def popcount(self, x): x = x - ((x >> 1) & 0x55555555) x = (x & 0x33333333) + ((x >> 2) & 0x33333333) x = x + (x >> 4) & 0x0f0f0f0f x = x + (x >> 8) x = x + (x >> 16) return x & 0x0000007f def set(self, k): self.bit[k >> 5] |= 1 << (k & 31) def build(self): for i in range(1, self.block): self.sum[i] = self.sum[i - 1] + self.popcount(self.bit[i - 1]) def access(self, k): return (self.bit[k >> 5] >> (k & 31)) & 1 def rank(self, k, v): r = self.sum[k >> 5] + self.popcount(self.bit[k >> 5] & ((1 << (k & 31)) - 1)) return r if v else k - r def select(self, k, v): if k < 0 or self.rank(self.size, v) <= k: return -1 l, r = 0, self.size while r - l > 1: m = (l + r) // 2 if self.rank(m, v) >= k + 1: r = m else: l = m return l class WaveletMatrix(): def __init__(self, log=32): self.size = 0 self.log = log self.mat = [None] * log self.mid = [None] * log def build(self, arr): self.size = len(arr) for lv in range(self.log)[::-1]: self.mat[lv] = FullyIndexableDictionary(self.size + 1) lt = [] rt = [] for i, a in enumerate(arr): if (a >> lv) & 1: self.mat[lv].set(i) rt.append(a) else: lt.append(a) self.mid[lv] = len(lt) self.mat[lv].build() arr = lt + rt def access(self, k): res = 0 for lv in range(self.log)[::-1]: if self.mat[lv].access(k): res |= 1 << lv k = self.mat[lv].rank(k, 1) + self.mid[lv] else: k = self.mat[lv].rank(k, 0) return res def rank(self, x, r): l = 0 for lv in range(self.log)[::-1]: if (x >> lv) & 1: l = self.mat[lv].rank(l, 1) + self.mid[lv] r = self.mat[lv].rank(r, 1) + self.mid[lv] else: l = self.mat[lv].rank(l, 0) r = self.mat[lv].rank(r, 0) return r - l def select(self, x, k): idx = 0 for lv in range(self.log)[::-1]: if (x >> lv) & 1: idx = self.mat[lv].rank(self.size, 0) + self.mat[lv].rank(idx, 1) else: idx = self.mat[lv].rank(idx, 0) idx += k for lv in range(self.log): if (x >> lv) & 1: idx = self.mat[lv].select(idx - self.mat[lv].rank(self.size, 0), 1) else: idx = self.mat[lv].select(idx, 0) return idx def freq(self, l, r, x): res = 0 for lv in range(self.log)[::-1]: if (x >> lv) & 1: res += self.mat[lv].rank(r, 0) - self.mat[lv].rank(l, 0) l = self.mat[lv].rank(l, 1) + self.mid[lv] r = self.mat[lv].rank(r, 1) + self.mid[lv] else: l = self.mat[lv].rank(l, 0) r = self.mat[lv].rank(r, 0) return res def quantile(self, l, r, k): res = 0 for lv in range(self.log)[::-1]: cnt = self.mat[lv].rank(r, 0) - self.mat[lv].rank(l, 0) if cnt <= k: res |= 1 << lv k -= cnt l = self.mat[lv].rank(l, 1) + self.mid[lv] r = self.mat[lv].rank(r, 1) + self.mid[lv] else: l = self.mat[lv].rank(l, 0) r = self.mat[lv].rank(r, 0) return res N, Q = map(int, input().split()) S = input() arr = [ord(s) for s in S] wm = WaveletMatrix() wm.build(arr) res = [] for _ in range(Q): l, r, x = map(int, input().split()) l -= 1; r -= 1; x -= 1 x = wm.quantile(l, r + 1, x) res.append(chr(x)) print('\n'.join(res))