結果
問題 | No.1471 Sort Queries |
ユーザー | None |
提出日時 | 2021-10-07 11:45:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 202 ms / 2,000 ms |
コード長 | 6,212 bytes |
コンパイル時間 | 440 ms |
コンパイル使用メモリ | 86,956 KB |
実行使用メモリ | 79,700 KB |
最終ジャッジ日時 | 2023-09-30 09:02:35 |
合計ジャッジ時間 | 8,831 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
70,852 KB |
testcase_01 | AC | 80 ms
70,936 KB |
testcase_02 | AC | 84 ms
70,456 KB |
testcase_03 | AC | 141 ms
75,932 KB |
testcase_04 | AC | 92 ms
76,072 KB |
testcase_05 | AC | 89 ms
75,464 KB |
testcase_06 | AC | 78 ms
70,608 KB |
testcase_07 | AC | 90 ms
75,440 KB |
testcase_08 | AC | 95 ms
75,704 KB |
testcase_09 | AC | 92 ms
75,540 KB |
testcase_10 | AC | 84 ms
75,728 KB |
testcase_11 | AC | 91 ms
76,004 KB |
testcase_12 | AC | 102 ms
76,640 KB |
testcase_13 | AC | 156 ms
78,552 KB |
testcase_14 | AC | 158 ms
78,024 KB |
testcase_15 | AC | 160 ms
78,400 KB |
testcase_16 | AC | 155 ms
78,540 KB |
testcase_17 | AC | 157 ms
77,968 KB |
testcase_18 | AC | 151 ms
78,464 KB |
testcase_19 | AC | 154 ms
78,076 KB |
testcase_20 | AC | 162 ms
78,348 KB |
testcase_21 | AC | 157 ms
78,120 KB |
testcase_22 | AC | 157 ms
78,384 KB |
testcase_23 | AC | 178 ms
78,432 KB |
testcase_24 | AC | 168 ms
78,240 KB |
testcase_25 | AC | 187 ms
78,276 KB |
testcase_26 | AC | 178 ms
78,460 KB |
testcase_27 | AC | 180 ms
79,624 KB |
testcase_28 | AC | 178 ms
78,928 KB |
testcase_29 | AC | 166 ms
77,680 KB |
testcase_30 | AC | 166 ms
77,624 KB |
testcase_31 | AC | 185 ms
78,116 KB |
testcase_32 | AC | 177 ms
77,756 KB |
testcase_33 | AC | 202 ms
79,640 KB |
testcase_34 | AC | 199 ms
79,248 KB |
testcase_35 | AC | 186 ms
78,800 KB |
testcase_36 | AC | 194 ms
79,360 KB |
testcase_37 | AC | 198 ms
79,700 KB |
testcase_38 | AC | 180 ms
77,936 KB |
testcase_39 | AC | 196 ms
79,360 KB |
ソースコード
class FullyIndexableDictionary(): def __init__(self, size, bit = None): self.size = size self.block = (size + 31) >> 5 self.b = [0] * self.block self.s = [0] * self.block if bit is not None: for i in range(self.size-1, -1, -1): if bit & 1: self.set(i) bit >>= 1 self.build() def set(self, p): self.b[p >> 5] |= 1 << (p & 31) def build(self): for i in range(1, self.block): self.s[i] = self.s[i - 1] + self.popcount(self.b[i - 1]) 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 access(self, p): return (self.b[p >> 5] >> (p & 31)) & 1 def _rank(self, p): # [0, p) mask = (1 << (p & 31)) - 1 return self.s[p >> 5] + self.popcount(self.b[p >> 5] & mask) def rank(self, p, b): if b: return self._rank(p) else: return p - self._rank(p) def select(self, x): # not verified lb, ub = 0, self.block while ub - lb > 1: mid = (ub + lb) // 2 if self.s[mid] <= x: lb = mid else: ub = mid b_id = lb lb = b_id * 32 ub = (b_id + 1) * 32 while ub - lb > 1: mid = (ub + lb) // 2 if self.rank(mid) <= x: lb = mid else: ub = mid return lb class WaveletMatrix: def __init__(self, lis, MAXLOG=32): self.N = len(lis) self.mat = list() self.zs = list() self.MAXLOG = MAXLOG self.build(lis) def build(self, _lis): lis = _lis[:] for dep in range(self.MAXLOG-1, -1, -1): ls = list() rs = list() fid = FullyIndexableDictionary(self.N + 1) for i in range(self.N): if lis[i] & (1 << dep): rs.append(lis[i]) fid.set(i) else: ls.append(lis[i]) fid.build() self.mat.append(fid) self.zs.append(len(ls)) lis = ls + rs return def rank(self, r, x): """ count number of occurrences of x in [0,r) """ return self._rank(0, r, x) def rangemax_k(self, l, r, k): """ k-th largest value in [l, r) (k in 1-indexed)""" ret = 0 for dep in range(self.MAXLOG): ret <<= 1 cntl = self.mat[dep].rank(l, 1) cntr = self.mat[dep].rank(r, 1) if cntr - cntl >= k: l = cntl + self.zs[dep] r = cntr + self.zs[dep] ret |= 1 else: l = l - cntl r = r - cntr k = k - (cntr - cntl) return ret def rangemin_k(self, l, r, k): """ k-th smallest value in [l, r) (k in 1-indexed)""" return self.rangemax_k(l,r,r-l-k+1) def rangefreq(self, l, r, x, y): """ count number of occurrences of [x,y) in [l,r) """ return self._freq_dfs(0, l, r, 0, x, y) def rangelist(self, l, r, x, y): """ count number of occurrences of each x in [x,y) in [l,r) """ return self._list_dfs(0, l, r, 0, x, y) def rangemax(self, l, r): ret = 0 for dep in range(self.MAXLOG): ret <<= 1 cntl = self.mat[dep].rank(l, 1) cntr = self.mat[dep].rank(r, 1) if cntl == cntr: l = l - cntl r = r - cntr else: l = cntl + self.zs[dep] r = cntr + self.zs[dep] ret |= 1 return ret def rangemin(self, l, r): ret = 0 for dep in range(self.MAXLOG): ret <<= 1 cntl = self.mat[dep].rank(l, 0) cntr = self.mat[dep].rank(r, 0) if cntl == cntr: l = l - cntl + self.zs[dep] r = r - cntr + self.zs[dep] ret |= 1 else: l = cntl r = cntr return ret def _rank(self, l, r, x): for dep in range(self.MAXLOG): bit = (x >> (self.MAXLOG - (dep + 1))) & 1 l = self.mat[dep].rank(l, bit) + self.zs[dep] * bit r = self.mat[dep].rank(r, bit) + self.zs[dep] * bit return r - l def _freq_dfs(self, dep, l, r, val, a, b): if l == r: return 0 if dep == self.MAXLOG: return r - l if a <= val < b else 0 mid = 1 << (self.MAXLOG - dep - 1) | val right = (1 << (self.MAXLOG - dep - 1)) - 1 | mid if right < a or b <= val: return 0 if a <= val and mid < b: return r - l cntl = self.mat[dep].rank(l, 1) cntr = self.mat[dep].rank(r, 1) return self._freq_dfs(dep + 1, l - cntl, r - cntr, val, a, b) + \ self._freq_dfs(dep + 1, cntl + self.zs[dep], cntr + self.zs[dep], mid, a, b) def _list_dfs(self, dep, l, r, val, a, b): vs = list() if l == r or b <= val: return vs if dep == self.MAXLOG: if a <= val < b: vs.append((val, r - l)) return vs mid = 1 << (self.MAXLOG - dep - 1) | val right = (1 << (self.MAXLOG - dep - 1)) - 1 | mid if right < a: return vs cntl = self.mat[dep].rank(l, 1) cntr = self.mat[dep].rank(r, 1) vs.extend(self._list_dfs(dep + 1, l - cntl, r - cntr, val, a, b)) vs.extend(self._list_dfs(dep + 1, cntl + self.zs[dep], cntr + self.zs[dep], mid, a, b)) return vs ############################################################################### N,Q=map(int, input().split()) P=[] for s in input().rstrip(): P.append(ord(s)-ord("a")) WM=WaveletMatrix(P) for _ in range(Q): l,r,x=map(int, input().split()) p=WM.rangemin_k(l-1,r,x) print(chr(p+ord("a")))