Part of course:
Lasers (ZCO 2017: India)
You are given an m x n grid with 3 types of cells - empty, black and white. There are b black cells, and w white cells.
A laser starts from an empty cell and travels towards the right. The laser stops on encountering either a black cell, or when it encounters its second white cell (or if neither happens, it stops when it reaches the boundary).
L(i, j) denotes the length travelled by a laser starting at (i, j). Note that the length is inclusive of both the columns, i.e. if the laser starts from (i, j) and ends at (i, k) when its length travelled is = k - j + 1.
Find the sum of L(i, j) for all i, j
Constraints: n, m <= 10^6 and b, w <= 10^5
Thanks Samarjeet for the problem statement.
Zonal Computing Olympiad is round 1 out of 3 for selection into Indian IOI team.