P15871 [MX-X26-T7] "Cfz Round 7" **Ultimate AVX2 Hardware Instruction Speedup**
Description
Given an array $v$ of length $n$ and a 2D plane containing $n$ "fish", the coordinates of the $i$-th "fish" are $(x_i, y_i)$, with a weight interval $[l_i, r_i]$.
There are $m$ queries. Each query provides $A_i, B_i, C_i$. Define $f(k, A_i, B_i, C_i) = 1$ if and only if $A_i x_k + B_i y_k + C_i < 0$; otherwise, $f(k, A_i, B_i, C_i) = 0$. Define the set $S$ as the set of all integers that lie in the union of $[l_k, r_k]$ over all $k$ satisfying $f(k, A_i, B_i, C_i) = 1$. Compute $\sum_{k \in S} v_k$.
Input Format
The first line contains an integer $c$, indicating the subtask ID of this test point. The samples satisfy $c = 0$.
The second line contains two integers $n, m$.
The next $n$ lines: the $i$-th line contains four integers $x_i, y_i, l_i, r_i$.
The next line contains $n$ integers $v_1, \dots, v_n$.
The next $m$ lines: the $i$-th line contains three integers $A_i, B_i, C_i$.
Output Format
For each query, output one line containing one integer, representing the answer.
Explanation/Hint
### Sample 1 Explanation
For the $1$-st query, only the $3$-rd "fish" and the $5$-th "fish" satisfy the condition. Their weight intervals are $[3, 5]$ and $[1, 5]$, so $S = \{1, 2, 3, 4, 5\}$. The answer is $v_1 + v_2 + v_3 + v_4 + v_5 = 22881$.
For the $2$-nd query, only the $2$-nd "fish" and the $3$-rd "fish" satisfy the condition. Their weight intervals are $[1, 1]$ and $[3, 5]$, so $S = \{1, 3, 4, 5\}$. The answer is $v_1 + v_3 + v_4 + v_5 = 18926$.
### Constraints
For all testdata:
- $1 \le n \le 5 \cdot 10^4$, $1 \le m \le 5 \cdot 10^5$.
- For all $1 \le i \le n$: $-10^6 \le x_i, y_i \le 10^6$, $1 \le l_i \le r_i \le n$.
- For all $1 \le i \le n$: $1 \le v_i \le 10^4$.
- For all $1 \le i \le m$: $-10^3 \le A_i, B_i \le 10^3$, ${A_i}^2 + {B_i}^2 > 0$, $1 \le C_i \le 10^9$.
For testdata other than Subtask 2, it is guaranteed that the $x, y$ coordinates of the $n$ "fish" are independently and uniformly randomly chosen within some preset ranges. Also, for the $i$-th "fish", $l_i, r_i$ and $x_i, y_i$ are independently randomly chosen, but the distribution of $l_i, r_i$ has no special restriction.
**This problem uses bundled evaluation.**
- Subtask 1 (10 points): $n, m \le 10^3$.
- Subtask 2 (18 points): For all $1 \le i \le n$, it is guaranteed that $\max(|x_i|, |y_i|) = 10^6$.
- Subtask 3 (18 points): For all $1 \le i \le m$, it is guaranteed that $|A_i| = |B_i| = 1$.
- Subtask 4 (24 points): $n \le 2 \cdot 10^4$, $m \le 2 \cdot 10^5$.
- Subtask 5 (30 points): No special restrictions.
Translated by ChatGPT 5