- Choose the aggregate stored for each interval or prefix.
- Build or initialize the structure from the input.
- Apply updates and combine the affected nodes to answer each query.
Code notes
- 77 lines of Python from the credited upstream file abc153_f.py.
- The implementation visibly relies on sequence storage, ordered lookup.
- No explicit loop blocks detected.
Complexity
Count the build once, then multiply the logarithmic update or query path by the number of operations.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4class BIT:5 """Binary Indexed Tree (Fenwick Tree)6 Args:7 size: List size (greater than 0).8 """9 10 def __init__(self, size: int):11 self.size = size12 self._bit = [0 for _ in range(self.size + 1)]13 14 def add(self, index: int, value: int) -> None:15 """Adds value to list with index i.16 Args:17 index: The number of index (1-indexed).18 value: A value19 Landau notation: O(log n)20 """21 22 while index <= self.size:23 self._bit[index] += value24 index += index & -index25 26 def sum(self, index) -> int:27 """Calculate the sum of elements from 1 to index.28 Args:29 index: The number of index (1-indexed).30 Returns:31 The sum of elements from 1 to index.32 Landau notation: O(log n)33 """34 35 summed = 036 37 while index > 0:38 summed += self._bit[index]39 index -= index & -index40 41 return summed42 43 44def main():45 from math import ceil46 from bisect import bisect_right47 import sys48 49 input = sys.stdin.readline50 51 n, d, a = map(int, input().split())52 p = sorted([list(map(int, input().split())) for _ in range(n)])53 xs = [xi for xi, _ in p]54 55 bit = BIT(n + 1)56 ans = 057 58 for index, (xi, hi) in enumerate(p, 1):59 hi -= bit.sum(index)60 61 if hi <= 0:62 continue63 64 bomb_count = ceil(hi / a)65 ans += bomb_count66 damage = a * bomb_count67 bit.add(index, damage)68 69 pos = bisect_right(xs, xi + 2 * d)70 bit.add(pos + 1, -damage)71 72 print(ans)73 74 75if __name__ == "__main__":76 main()77