 # Help! I need to solve a question with time complexity less than n^2

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

I think the key observation is:

Consider a single horizontal stripe. Every third piece belongs to respective color, ...BGRBGRBGR.... For this row you’ll have some total for red, green and blue on the form: r\times Y_1, g\times Y_1 and b\times Y_1.

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.