For this problem, I heard that using a difference array can solve the problem but I can't seem to figure out how to solve this problem. Could anyone give me some advice? Please keep it simple since I am only a high school student preparing for the national infomatics Olympiad.
Given an array of numbers, we can construct a new array by replacing each element by the difference between itself and the previous element, except for the first element, which we simply ignore. This is called the difference array, because it contains the first differences of the original array. We will denote the difference array of array A by D(A). For example, the difference array of A = [9, 2, 6, 3, 1, 5, 0, 7] is D(A) = [2-9, 6-2, 3-6, 1-3, 5-1, 0-5, 7-0], or [-7, 4, -3, -2, 4, -5, 7]. Source
I've found a solution in Python , but I can't understand it.
Canadian Computing Competition: 2014 Stage 1, Senior #4:
You are laying N rectangular pieces of grey-tinted glass to make a stained glass window. Each piece of glass adds an integer value "tint-factor". Where two pieces of glass overlap, the tint-factor is the sum of their tint-factors.
You know the desired position for each piece of glass and these pieces of glass are placed such that the sides of each rectangle are parallel to either the x-axis or the y-axis (that is, there are no "diagonal" pieces of glass).
You would like to know the total area of the finished stained glass window with a tint-factor of at least T.
The first line of input is the integer $N$ ($1\leq N\leq 10^3$), the number of pieces of glass. The second line of input is the integer $T$ ($1\leq T\leq 10^9$), the threshold for the tint-factor. Each of the next $N$ lines contain five integers, representing the position of the top-left and bottom-right corners of the $i$-th piece of tinted glass followed by the tint-factor of that piece of glass. Specifically, the integers are placed in the order $x_1$ $y_1$ $x_2$ $y_2$ $t$, where the top-left corner is at $(x_1,y_1)$ and the bottom-right corner is at $(x_2,y_2)$, and tint-factor is $t$. You can assume that $1\leq t\leq 10^6$. The top-most, left-most coordinate where glass can be placed is $(0,0)$ and you may assume $0\leq x_1<x_2\leq K$ and $0<y_1<y_2\leq K$, and ...
Output Specification: Output the total area of the finished stained glass window which has a tint-factor of at least $T$.
I have an implementation but I'm not quite sure how it works. Any explanation would be greatly appreciated.