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