Dish Shopping
Contest: Codeforces Round 548 (Div. 2)
Difficulty rating: 2500
Tags: data structures, divide and conquer

There are $$$m$$$ people living in a city. There are $$$n$$$ dishes sold in the city. Each dish $$$i$$$ has a price $$$p_i$$$, a standard $$$s_i$$$ and a beauty $$$b_i$$$. Each person $$$j$$$ has an income of $$$inc_j$$$ and a preferred beauty $$$pref_j$$$.

A person would never buy a dish whose standard is less than the person's income. Also, a person can't afford a dish with a price greater than the income of the person. In other words, a person $$$j$$$ can buy a dish $$$i$$$ only if $$$p_i \leq inc_j \leq s_i$$$.

Also, a person $$$j$$$ can buy a dish $$$i$$$, only if $$$|b_i-pref_j| \leq (inc_j-p_i)$$$. In other words, if the price of the dish is less than the person's income by $$$k$$$, the person will only allow the absolute difference of at most $$$k$$$ between the beauty of the dish and his/her preferred beauty.

Print the number of dishes that can be bought by each person in the city.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$), the number of dishes available in the city and the number of people living in the city.

The second line contains $$$n$$$ integers $$$p_i$$$ ($$$1 \leq p_i \leq 10^9$$$), the price of each dish.

The third line contains $$$n$$$ integers $$$s_i$$$ ($$$1 \leq s_i \leq 10^9$$$), the standard of each dish.

The fourth line contains $$$n$$$ integers $$$b_i$$$ ($$$1 \leq b_i \leq 10^9$$$), the beauty of each dish.

The fifth line contains $$$m$$$ integers $$$inc_j$$$ ($$$1 \leq inc_j \leq 10^9$$$), the income of every person.

The sixth line contains $$$m$$$ integers $$$pref_j$$$ ($$$1 \leq pref_j \leq 10^9$$$), the preferred beauty of every person.

It is guaranteed that for all integers $$$i$$$ from $$$1$$$ to $$$n$$$, the following condition holds: $$$p_i \leq s_i$$$.

Output format:
Print $$$m$$$ integers, the number of dishes that can be bought by every person living in the city.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the first person can buy dish $$$2$$$, the second person can buy dishes $$$1$$$ and $$$2$$$ and the third person can buy no dishes.

In the second example, the first person can buy no dishes, the second person can buy dishes $$$1$$$ and $$$4$$$, and the third person can buy dishes $$$1$$$, $$$2$$$ and $$$4$$$.

Example input:
3 3
2 1 3
2 4 4
2 1 1
2 2 3
1 2 4

Example output:
1 2 0

Example input:
4 3
1 2 1 1
3 3 1 3
2 1 3 2
1 1 3
1 2 1

Example output:
0 2 3

Editorial:
Let's consider a matrix where $$$i$$$-th row represents price $$$i$$$ and $$$j$$$-th column represents beauty $$$j$$$, such that the value of $$$c[i][j]$$$ represents the number of dishes that can be bought by a person having income $$$i$$$ and preferred beauty $$$j$$$. Then, adding a dish with price $$$p$$$, standard $$$s$$$ and beauty $$$b$$$ is similar to adding $$$+1$$$ in each cell in the triangle formed by vertices $$$P(p, b)$$$, $$$Q(s, b - s + p)$$$ and $$$R(s, b + s - p)$$$. Now, we need to update the given triangles with $$$+1$$$ in a matrix efficiently. Let's do this offline.
Note that for a triangle with vertices $$$P(p, b)$$$, $$$Q(s, b - s + p)$$$ and $$$R(s, b + s - p)$$$, the column updated in $$$p$$$-th row is $$$b$$$. The columns updated in $$$(p + 1)$$$-th row are $$$b - 1$$$, $$$b$$$ and $$$b + 1$$$. So, if the columns updated in $$$i$$$-th row are $$$x \ldots y$$$, then the columns updated in $$$i + 1$$$-th row will be $$$(x - 1) \ldots (y + 1)$$$. For updating a range $$$l \ldots r$$$ in a row $$$i$$$, we can update $$$mat[i][l]$$$ with $$$+1$$$ and $$$mat[i][r + 1]$$$ with $$$-1$$$. And then when we do prefix sum in that row we get actual values for each cell.
We can use similar approach here. Note that instead of updating $$$mat[i][l]$$$ with $$$+1$$$, we can update some array $$$larr[i + l]$$$ with $$$+1$$$, similarly instead of updating $$$mat[i][r + 1]$$$ with $$$-1$$$, we can update some array $$$rarr[r + 1 - i]$$$ with $$$-1$$$. In this way, we can provide updates for each row in triangle instead of just one row. The value of a cell $$$mat[i][j]$$$ will be addition of prefix sum of $$$larr$$$ in range $$$[0, i+j]$$$ and prefix sum of $$$rarr$$$ in range $$$[0, j-i]$$$.
Let's create four events for each triangle. For, a triangle with vertices $$$P(p, b)$$$, $$$Q(s, b - s + p)$$$ and $$$R(s, b + s - p)$$$, the events added will be $$$larr[p + b] \texttt{+=} 1$$$ at cell $$$(p, b)$$$, $$$rarr[b + 1 - p] \texttt{-=} 1$$$ at cell $$$(p, b + 1)$$$, $$$larr[p + b] \texttt{-=} 1$$$ at cell $$$(s + 1, b - s - 1 + p)$$$, $$$rarr[b + 1 - p] \texttt{-=} 1$$$ at cell $$$(s + 1, b + s + 1 - p)$$$. Also, we add query events for each person $$$i$$$ at cell $$$(inc_i, pb_i)$$$. Let's sort this events on the basis of rows of the cell and then for the same row we handle triangle events first and then handle query events. For maintaining prefix sum in $$$larr$$$ and $$$rarr$$$, we can use compression and a datastructure like fenwick tree.
Overall Complexity: $$$O((n + m) \cdot log(n + m))$$$