CEOI 2020: Fancy fence

Problem statement: 

Everybody knows that Balázs has the fanciest fence in the whole town. It’s built up from $N$ fancy sections. The sections are rectangles standing closely next to each other on the ground. The $i^{\text{th}}$ section has integer height $h_i$ and integer width $w_i$ . We are looking for fancy rectangles on this fancy fence. A rectangle is fancy if:

• its sides are either horizontal or vertical and have integer lengths
• the distance between the rectangle and the ground is integer
• the distance between the rectangle and the left side of the first section is integer
• it’s lying completely on sections 

What is the number of fancy rectangles? This number can be very big, so we are interested in it modulo $10^9 + 7$.

Input: The first line contains $N$, the number of sections. The second line contains $N$ space-separated integers, the $i^{\text{th}}$ number is $h_i$ . The third line contains $N$ space-separated integers, the $i^{\text{th}}$ number is $w_i$.

Constraints:

$1 \leq N \leq 10^5$

$1 \leq h_i, wi \leq 10^9$

Time limit: 0.1 s

Memory limit: 32 MiB

My approach:

It seems reasonable to first figure out how many fancy rectangles an $h_i\times w_i$ fancy section has. If we draw an $h_i\times w_i$ rectangle as follows.

We see that the pair of points chosen for both sides uniquely determine a fancy rectangle. Thus we have

$$F(h_i, w_i)={h_i + 1 \choose 2}\cdot{w_i + 1 \choose 2}$$

fancy rectangles for an $h_i\times w_i$ fancy section.

When we place fancy sections next to each other in a line, we can have fancy rectangles positioned across two or more fancy sections. Thus we have to count these too. Consider the following example input where all $h_i<h_{i+1}$.

Each square is $1\times 1$ and the purple lines indicate the separation between consecutive fancy sections. Let $W=w_1+w_2+...+w_N$. Notice $F(h_2, W-w_1)$ counts all fancy rectangles counted by $F(h_1, W)$ except the rectangles that start in the first fancy section. We use this to get an answer for when $h_i<h_{i+1}$.

$$\sum_{i=1}^{N}{F(h_i, W-w_{i-1})-F(h_{i-1}, W-w_{i-1})}$$

where $w_0=h_0=0$. But what about the general case where we are not given that $h_i<h_{i+1}$?