broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    W = x['W']
    buckets = []
    out = []
    for t, bit in enumerate(x['bits'], 1):
        while buckets and buckets[-1][1] <= t - W:
            buckets.pop()
        if bit:
            buckets.insert(0, [1, t])
            size = 1
            while True:
                idx = [i for i, bk in enumerate(buckets) if bk[0] == size]
                if len(idx) <= 3:
                    break
                a, z = idx[-2], idx[-1]
                buckets[a] = [size * 2, buckets[a][1]]
                del buckets[z]
                size *= 2
        if t in x['queries']:
            if buckets:
                total = sum(bk[0] for bk in buckets)
                out.append([t, total - buckets[-1][0] // 2])
            else:
                out.append([t, 0])
    return [out, buckets]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 W=10',
   {'W': 10,
    'bits': [1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 15]},
   [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 10]},
   [[[4, 3], [8, 1], [10, 0]], []]],
  ['empty window', {'W': 3, 'bits': [0, 0, 0, 0, 0], 'queries': [2, 4]}, [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 4], [25, 5]], [[1, 25], [1, 24], [2, 23], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 12], [40, 8]], [[1, 40], [1, 38], [2, 33], [2, 30], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 2], [20, 4]], [[1, 19], [2, 18], [2, 16]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 16]},
   [[[7, 5], [16, 12]], [[1, 16], [1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 11]},
   [[[4, 3], [8, 1], [11, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 6], [30, 5]], [[1, 29], [1, 28], [2, 27], [2, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 7], [22, 6], [25, 4]], [[1, 24], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 13], [37, 12], [40, 8]], [[1, 40], [1, 39], [2, 37], [2, 33], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 3]], [[1, 20], [1, 19], [2, 18]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 17]},
   [[[7, 5], [17, 13]], [[1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 12]},
   [[[4, 3], [8, 1], [12, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             0,
             1],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 5]], [[1, 30], [1, 27], [2, 24], [2, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 4], [22, 7], [25, 5]], [[1, 25], [1, 22], [2, 21], [2, 19]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             0],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 9], [40, 11]], [[1, 39], [2, 38], [2, 36], [4, 31], [4, 25]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 4], [17, 6], [20, 5]], [[1, 20], [1, 19], [2, 17], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 18]},
   [[[7, 5], [18, 14]], [[1, 18], [1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 13]},
   [[[4, 3], [8, 1], [13, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 10], [40, 8]], [[1, 40], [1, 38], [2, 37], [2, 35], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 3], [20, 2]], [[1, 20], [2, 19]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 19]},
   [[[7, 5], [19, 15]], [[1, 19], [2, 18], [4, 16], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 14]},
   [[[4, 3], [8, 1], [14, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    W = x['W']
    buckets = []
    out = []
    for t, bit in enumerate(x['bits'], 1):
        while buckets and buckets[-1][1] <= t - W:
            buckets.pop()
        if bit:
            buckets.insert(0, [1, t])
            size = 1
            while True:
                idx = [i for i, bk in enumerate(buckets) if bk[0] == size]
                if len(idx) <= 1:
                    break
                a, z = idx[-2], idx[-1]
                buckets[a] = [size * 2, buckets[a][1]]
                del buckets[z]
                size *= 2
        if t in x['queries']:
            if buckets:
                total = sum(bk[0] for bk in buckets)
                out.append([t, total - buckets[-1][0] // 2])
            else:
                out.append([t, 0])
    return [out, buckets]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 W=10',
   {'W': 10,
    'bits': [1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 15]},
   [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 10]},
   [[[4, 3], [8, 1], [10, 0]], []]],
  ['empty window', {'W': 3, 'bits': [0, 0, 0, 0, 0], 'queries': [2, 4]}, [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 4], [25, 5]], [[1, 25], [1, 24], [2, 23], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 12], [40, 8]], [[1, 40], [1, 38], [2, 33], [2, 30], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 2], [20, 4]], [[1, 19], [2, 18], [2, 16]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 16]},
   [[[7, 5], [16, 12]], [[1, 16], [1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 11]},
   [[[4, 3], [8, 1], [11, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 6], [30, 5]], [[1, 29], [1, 28], [2, 27], [2, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 7], [22, 6], [25, 4]], [[1, 24], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 13], [37, 12], [40, 8]], [[1, 40], [1, 39], [2, 37], [2, 33], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 3]], [[1, 20], [1, 19], [2, 18]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 17]},
   [[[7, 5], [17, 13]], [[1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 12]},
   [[[4, 3], [8, 1], [12, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             0,
             1],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 5]], [[1, 30], [1, 27], [2, 24], [2, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 4], [22, 7], [25, 5]], [[1, 25], [1, 22], [2, 21], [2, 19]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             0],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 9], [40, 11]], [[1, 39], [2, 38], [2, 36], [4, 31], [4, 25]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 4], [17, 6], [20, 5]], [[1, 20], [1, 19], [2, 17], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 18]},
   [[[7, 5], [18, 14]], [[1, 18], [1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 13]},
   [[[4, 3], [8, 1], [13, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 10], [40, 8]], [[1, 40], [1, 38], [2, 37], [2, 35], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 3], [20, 2]], [[1, 20], [2, 19]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 19]},
   [[[7, 5], [19, 15]], [[1, 19], [2, 18], [4, 16], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 14]},
   [[[4, 3], [8, 1], [14, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The histogram holds more buckets than the invariant allows and estimates change.

Input {W, bits, queries}; timestamps start at 1. Buckets are [size, timestamp of most recent 1], newest first. Before processing time t, buckets with timestamp <= t - W expire. A 1 bit adds [1, t]; while more than two buckets share a size, the two oldest of that size merge into one of double size keeping the more recent timestamp, cascading upward. At a query time the estimate is the total size minus floor(oldest size / 2). Return [[t, estimate] per query, final buckets].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    W = x['W']
    buckets = []
    out = []
    for t, bit in enumerate(x['bits'], 1):
        while buckets and buckets[-1][1] <= t - W:
            buckets.pop()
        if bit:
            buckets.insert(0, [1, t])
            size = 1
            while True:
                idx = [i for i, bk in enumerate(buckets) if bk[0] == size]
                if len(idx) <= 2:
                    break
                a, z = idx[-2], idx[-1]
                buckets[a] = [size * 2, buckets[a][1]]
                del buckets[z]
                break
        if t in x['queries']:
            if buckets:
                total = sum(bk[0] for bk in buckets)
                out.append([t, total - buckets[-1][0] // 2])
            else:
                out.append([t, 0])
    return [out, buckets]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 W=10',
   {'W': 10,
    'bits': [1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 15]},
   [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 10]},
   [[[4, 3], [8, 1], [10, 0]], []]],
  ['empty window', {'W': 3, 'bits': [0, 0, 0, 0, 0], 'queries': [2, 4]}, [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 4], [25, 5]], [[1, 25], [1, 24], [2, 23], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 12], [40, 8]], [[1, 40], [1, 38], [2, 33], [2, 30], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 2], [20, 4]], [[1, 19], [2, 18], [2, 16]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 16]},
   [[[7, 5], [16, 12]], [[1, 16], [1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 11]},
   [[[4, 3], [8, 1], [11, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 6], [30, 5]], [[1, 29], [1, 28], [2, 27], [2, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 7], [22, 6], [25, 4]], [[1, 24], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 13], [37, 12], [40, 8]], [[1, 40], [1, 39], [2, 37], [2, 33], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 3]], [[1, 20], [1, 19], [2, 18]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 17]},
   [[[7, 5], [17, 13]], [[1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 12]},
   [[[4, 3], [8, 1], [12, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             0,
             1],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 5]], [[1, 30], [1, 27], [2, 24], [2, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 4], [22, 7], [25, 5]], [[1, 25], [1, 22], [2, 21], [2, 19]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             0],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 9], [40, 11]], [[1, 39], [2, 38], [2, 36], [4, 31], [4, 25]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 4], [17, 6], [20, 5]], [[1, 20], [1, 19], [2, 17], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 18]},
   [[[7, 5], [18, 14]], [[1, 18], [1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 13]},
   [[[4, 3], [8, 1], [13, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 10], [40, 8]], [[1, 40], [1, 38], [2, 37], [2, 35], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 3], [20, 2]], [[1, 20], [2, 19]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 19]},
   [[[7, 5], [19, 15]], [[1, 19], [2, 18], [4, 16], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 14]},
   [[[4, 3], [8, 1], [14, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    W = x['W']
    buckets = []
    out = []
    for t, bit in enumerate(x['bits'], 1):
        while buckets and buckets[-1][1] <= t - W:
            buckets.pop()
        if bit:
            buckets.insert(0, [1, t])
            size = 1
            while True:
                idx = [i for i, bk in enumerate(buckets) if bk[0] == size]
                if len(idx) <= 2:
                    break
                a, z = idx[-2], idx[-1]
                buckets[a] = [size * 2, buckets[a][1]]
                del buckets[z]
                size += 1
        if t in x['queries']:
            if buckets:
                total = sum(bk[0] for bk in buckets)
                out.append([t, total - buckets[-1][0] // 2])
            else:
                out.append([t, 0])
    return [out, buckets]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 W=10',
   {'W': 10,
    'bits': [1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 15]},
   [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 10]},
   [[[4, 3], [8, 1], [10, 0]], []]],
  ['empty window', {'W': 3, 'bits': [0, 0, 0, 0, 0], 'queries': [2, 4]}, [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 4], [25, 5]], [[1, 25], [1, 24], [2, 23], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 12], [40, 8]], [[1, 40], [1, 38], [2, 33], [2, 30], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 2], [20, 4]], [[1, 19], [2, 18], [2, 16]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 16]},
   [[[7, 5], [16, 12]], [[1, 16], [1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 11]},
   [[[4, 3], [8, 1], [11, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 6], [30, 5]], [[1, 29], [1, 28], [2, 27], [2, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 7], [22, 6], [25, 4]], [[1, 24], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 13], [37, 12], [40, 8]], [[1, 40], [1, 39], [2, 37], [2, 33], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 3]], [[1, 20], [1, 19], [2, 18]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 17]},
   [[[7, 5], [17, 13]], [[1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 12]},
   [[[4, 3], [8, 1], [12, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             0,
             1],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 5]], [[1, 30], [1, 27], [2, 24], [2, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 4], [22, 7], [25, 5]], [[1, 25], [1, 22], [2, 21], [2, 19]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             0],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 9], [40, 11]], [[1, 39], [2, 38], [2, 36], [4, 31], [4, 25]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 4], [17, 6], [20, 5]], [[1, 20], [1, 19], [2, 17], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 18]},
   [[[7, 5], [18, 14]], [[1, 18], [1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 13]},
   [[[4, 3], [8, 1], [13, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 10], [40, 8]], [[1, 40], [1, 38], [2, 37], [2, 35], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 3], [20, 2]], [[1, 20], [2, 19]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 19]},
   [[[7, 5], [19, 15]], [[1, 19], [2, 18], [4, 16], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 14]},
   [[[4, 3], [8, 1], [14, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
After a merge, three buckets of the doubled size can coexist.

Input {W, bits, queries}; timestamps start at 1. Buckets are [size, timestamp of most recent 1], newest first. Before processing time t, buckets with timestamp <= t - W expire. A 1 bit adds [1, t]; while more than two buckets share a size, the two oldest of that size merge into one of double size keeping the more recent timestamp, cascading upward. At a query time the estimate is the total size minus floor(oldest size / 2). Return [[t, estimate] per query, final buckets].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    W = x['W']
    buckets = []
    out = []
    for t, bit in enumerate(x['bits'], 1):
        while buckets and buckets[-1][1] < t - W:
            buckets.pop()
        if bit:
            buckets.insert(0, [1, t])
            size = 1
            while True:
                idx = [i for i, bk in enumerate(buckets) if bk[0] == size]
                if len(idx) <= 2:
                    break
                a, z = idx[-2], idx[-1]
                buckets[a] = [size * 2, buckets[a][1]]
                del buckets[z]
                size *= 2
        if t in x['queries']:
            if buckets:
                total = sum(bk[0] for bk in buckets)
                out.append([t, total - buckets[-1][0] // 2])
            else:
                out.append([t, 0])
    return [out, buckets]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 W=10',
   {'W': 10,
    'bits': [1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 15]},
   [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 10]},
   [[[4, 3], [8, 1], [10, 0]], []]],
  ['empty window', {'W': 3, 'bits': [0, 0, 0, 0, 0], 'queries': [2, 4]}, [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 4], [25, 5]], [[1, 25], [1, 24], [2, 23], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 12], [40, 8]], [[1, 40], [1, 38], [2, 33], [2, 30], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 2], [20, 4]], [[1, 19], [2, 18], [2, 16]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 16]},
   [[[7, 5], [16, 12]], [[1, 16], [1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 11]},
   [[[4, 3], [8, 1], [11, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 6], [30, 5]], [[1, 29], [1, 28], [2, 27], [2, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 7], [22, 6], [25, 4]], [[1, 24], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 13], [37, 12], [40, 8]], [[1, 40], [1, 39], [2, 37], [2, 33], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 3]], [[1, 20], [1, 19], [2, 18]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 17]},
   [[[7, 5], [17, 13]], [[1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 12]},
   [[[4, 3], [8, 1], [12, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             0,
             1],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 5]], [[1, 30], [1, 27], [2, 24], [2, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 4], [22, 7], [25, 5]], [[1, 25], [1, 22], [2, 21], [2, 19]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             0],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 9], [40, 11]], [[1, 39], [2, 38], [2, 36], [4, 31], [4, 25]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 4], [17, 6], [20, 5]], [[1, 20], [1, 19], [2, 17], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 18]},
   [[[7, 5], [18, 14]], [[1, 18], [1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 13]},
   [[[4, 3], [8, 1], [13, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 10], [40, 8]], [[1, 40], [1, 38], [2, 37], [2, 35], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 3], [20, 2]], [[1, 20], [2, 19]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 19]},
   [[[7, 5], [19, 15]], [[1, 19], [2, 18], [4, 16], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 14]},
   [[[4, 3], [8, 1], [14, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    W = x['W']
    buckets = []
    out = []
    for t, bit in enumerate(x['bits'], 1):
        while bit and buckets and buckets[-1][1] <= t - W:
            buckets.pop()
        if bit:
            buckets.insert(0, [1, t])
            size = 1
            while True:
                idx = [i for i, bk in enumerate(buckets) if bk[0] == size]
                if len(idx) <= 2:
                    break
                a, z = idx[-2], idx[-1]
                buckets[a] = [size * 2, buckets[a][1]]
                del buckets[z]
                size *= 2
        if t in x['queries']:
            if buckets:
                total = sum(bk[0] for bk in buckets)
                out.append([t, total - buckets[-1][0] // 2])
            else:
                out.append([t, 0])
    return [out, buckets]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 W=10',
   {'W': 10,
    'bits': [1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 15]},
   [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 10]},
   [[[4, 3], [8, 1], [10, 0]], []]],
  ['empty window', {'W': 3, 'bits': [0, 0, 0, 0, 0], 'queries': [2, 4]}, [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 4], [25, 5]], [[1, 25], [1, 24], [2, 23], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 12], [40, 8]], [[1, 40], [1, 38], [2, 33], [2, 30], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 2], [20, 4]], [[1, 19], [2, 18], [2, 16]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 16]},
   [[[7, 5], [16, 12]], [[1, 16], [1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 11]},
   [[[4, 3], [8, 1], [11, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 6], [30, 5]], [[1, 29], [1, 28], [2, 27], [2, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 7], [22, 6], [25, 4]], [[1, 24], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 13], [37, 12], [40, 8]], [[1, 40], [1, 39], [2, 37], [2, 33], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 3]], [[1, 20], [1, 19], [2, 18]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 17]},
   [[[7, 5], [17, 13]], [[1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 12]},
   [[[4, 3], [8, 1], [12, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             0,
             1],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 5]], [[1, 30], [1, 27], [2, 24], [2, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 4], [22, 7], [25, 5]], [[1, 25], [1, 22], [2, 21], [2, 19]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             0],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 9], [40, 11]], [[1, 39], [2, 38], [2, 36], [4, 31], [4, 25]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 4], [17, 6], [20, 5]], [[1, 20], [1, 19], [2, 17], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 18]},
   [[[7, 5], [18, 14]], [[1, 18], [1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 13]},
   [[[4, 3], [8, 1], [13, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 10], [40, 8]], [[1, 40], [1, 38], [2, 37], [2, 35], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 3], [20, 2]], [[1, 20], [2, 19]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 19]},
   [[[7, 5], [19, 15]], [[1, 19], [2, 18], [4, 16], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 14]},
   [[[4, 3], [8, 1], [14, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A 1 that is exactly W ticks old is still counted.

Input {W, bits, queries}; timestamps start at 1. Buckets are [size, timestamp of most recent 1], newest first. Before processing time t, buckets with timestamp <= t - W expire. A 1 bit adds [1, t]; while more than two buckets share a size, the two oldest of that size merge into one of double size keeping the more recent timestamp, cascading upward. At a query time the estimate is the total size minus floor(oldest size / 2). Return [[t, estimate] per query, final buckets].

split: open-access