King Color died and left 3 princes behind Red (22 years old), Green (21), and Blue (20). They inherited a huge piece of land with rectangular shape; the three children had a dispute on how to divide the land between them, until their father’s advisor suggested to use the following method: He partitioned the land into n vertical stripes of random lengths: X1, X2, … Xn, meters and n horizontal stripes of random lengths Y1, Y2, …, Yn meters. These stripes split the land into n x n rectangles. The intersection of vertical stripe i and horizontal stripe j has code number (i + j) mod 3, and hence is given to the prince with the same first digit in his age. For example area X1 Y1 has the code (1+1)%3 = 2, hence it is given to prince Red (22), area Y6 X4 has the code 1 hence it is given to prince Green (21). Your task is to calculate the area of land given to each prince. The input consists of several problem instances, each starts with the integer n on the first line, followed by two lines each has n integers for the values of X1, ... , Xn, separated with single spaces, followed by the values of Y1, ... , Yn on the next line separated with single spaces. Then next problem instance follows starting with a new n. Problem instances terminate when n = 0. Problem boundaries are: 3≤ n≤ 250000 1≤Yi ,Xi ≤10 asked 20 Sep '18, 16:44

I think the key observation is: Consider a single horizontal stripe. Every third piece belongs to respective color, What changes for the next line? Depending on $n$ the color pattern either stays in place or is shifted left or right. You can use the previous $r$, $g$, $b$ (in that order or shifted left or right) to calculate the results for the next row in constant time. answered 21 Sep '18, 10:24
