結果
問題 | No.2154 あさかつの参加人数 |
ユーザー | titan23 |
提出日時 | 2023-01-20 14:11:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,239 ms / 2,000 ms |
コード長 | 4,131 bytes |
コンパイル時間 | 1,067 ms |
コンパイル使用メモリ | 85,864 KB |
実行使用メモリ | 95,288 KB |
最終ジャッジ日時 | 2023-09-05 07:47:20 |
合計ジャッジ時間 | 32,951 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,192 ms
95,112 KB |
testcase_01 | AC | 1,239 ms
95,028 KB |
testcase_02 | AC | 1,186 ms
95,100 KB |
testcase_03 | AC | 1,196 ms
94,952 KB |
testcase_04 | AC | 1,171 ms
94,996 KB |
testcase_05 | AC | 466 ms
83,116 KB |
testcase_06 | AC | 904 ms
88,104 KB |
testcase_07 | AC | 689 ms
90,900 KB |
testcase_08 | AC | 686 ms
91,904 KB |
testcase_09 | AC | 391 ms
89,996 KB |
testcase_10 | AC | 640 ms
89,832 KB |
testcase_11 | AC | 1,072 ms
93,852 KB |
testcase_12 | AC | 884 ms
89,868 KB |
testcase_13 | AC | 560 ms
86,280 KB |
testcase_14 | AC | 929 ms
89,784 KB |
testcase_15 | AC | 672 ms
90,700 KB |
testcase_16 | AC | 911 ms
91,000 KB |
testcase_17 | AC | 966 ms
89,476 KB |
testcase_18 | AC | 1,029 ms
91,884 KB |
testcase_19 | AC | 263 ms
84,112 KB |
testcase_20 | AC | 897 ms
92,392 KB |
testcase_21 | AC | 366 ms
89,532 KB |
testcase_22 | AC | 517 ms
95,288 KB |
testcase_23 | AC | 1,025 ms
91,828 KB |
testcase_24 | AC | 1,112 ms
93,572 KB |
ソースコード
import sys input = lambda: sys.stdin.readline().rstrip() from typing import List, Iterable class FenwickTreeRAQ: '''Build a new FenwickTreeRAQ.''' def __init__(self, n: int, a: Iterable[int]=[]): self._n = n self.bit0 = FenwickTree(n+1) self.bit1 = FenwickTree(n+1) for i, a_ in enumerate(a): self.add(i, a_) '''Add x to a[k]. / O(logN)''' def add(self, k: int, x: int) -> None: self.add_range(k, k+1, x) '''Add x to [l, r). / O(logN)''' def add_range(self, l: int, r: int, x: int) -> None: self.bit0.add(l, -x*l) self.bit0.add(r, x*r) self.bit1.add(l, x) self.bit1.add(r, -x) '''Return sum [l, r). / O(logN)''' def sum(self, l: int, r: int) -> int: return self.bit0.pref(r) + r*self.bit1.pref(r) - self.bit0.pref(l) - l*self.bit1.pref(l) def to_l(self) -> List[int]: return [self.sum(i, i+1) for i in range(self._n)] def __getitem__(self, k: int): return self.sum(k, k+1) def __str__(self): return '[' + ', '.join(map(str, (self.__getitem__(i) for i in range(self._n)))) + ']' def __repr__(self): return 'FenwickTreeRAQ(' + str(self) + ')' from typing import List, Union class FenwickTree: '''Build a new FenwickTree. / O(N)''' def __init__(self, _n_or_a: Union[List[int], int]): if isinstance(_n_or_a, int): self._size = _n_or_a self._tree = [0] * (self._size+1) else: a = list(_n_or_a) self._size = len(a) self._tree = [0] + a for i in range(1, self._size): if i + (i & -i) <= self._size: self._tree[i + (i & -i)] += self._tree[i] self._s = 1 << (self._size-1).bit_length() '''Return sum([0, r)) of a. / O(logN)''' def pref(self, r: int) -> int: # assert r <= self._size ret = 0 while r > 0: ret += self._tree[r] r -= r & -r return ret '''Return sum([l, n)) of a. / O(logN)''' def suff(self, l: int) -> int: # assert 0 <= l < self._size return self.pref(self._size) - self.pref(l) '''Return sum([l, r)] of a. / O(logN)''' def sum(self, l: int, r: int) -> int: # assert 0 <= l <= r <= self._size return self.pref(r) - self.pref(l) def __getitem__(self, k: int) -> int: return self.sum(k, k+1) '''Add x to a[k]. / O(logN)''' def add(self, k: int, x: int) -> None: # assert 0 <= k < self._size k += 1 while k <= self._size: self._tree[k] += x k += k & -k '''Update A[k] to x. / O(logN)''' def set(self, k: int, x: int) -> None: pre = self.get(k) self.add(k, x - pre) '''bisect_left(acc)''' def bisect_left(self, w: int) -> int: i = 0 s = self._s while s: if i + s <= self._size and self._tree[i + s] < w: w -= self._tree[i + s] i += s s >>= 1 return i if w else None '''bisect_right(acc)''' def bisect_right(self, w: int) -> int: i = 0 s = self._s while s: if i + s <= self._size and self._tree[i + s] <= w: w -= self._tree[i + s] i += s s >>= 1 return i def show(self) -> None: print('[' + ', '.join(map(str, (self.pref(i) for i in range(self._size+1)))) + ']') def to_l(self) -> List[int]: return [self.__getitem__(i) for i in range(self._size)] @classmethod def inversion_num(self, a: List[int], compress: bool=False) -> int: ans = 0 if compress: a_ = sorted(set(a)) z = {e: i for i, e in enumerate(a_)} fw = FenwickTree(len(a_)) for i, e in enumerate(a): ans += i - fw.pref(z[e]) fw.add(z[e], 1) else: fw = FenwickTree(len(a)) for i, e in enumerate(a): ans += i - fw.pref(e) fw.add(e, 1) return ans def __str__(self): sub = [self.pref(i) for i in range(self._size+1)] return '[' + ', '.join(map(str, (sub[i+1]-sub[i] for i in range(self._size)))) + ']' def __repr__(self): return 'FenwickTree(' + str(self) + ')' # ----------------------- # n, m = map(int, input().split()) fw = FenwickTreeRAQ(n+1) for _ in range(m): l, r = map(int, input().split()) fw.add_range(r, l+1, 1) for i in range(n, 0, -1): print(fw[i])