P8513 [Ynoi Easy Round 2021] TEST_136

Given $n$ points $(x_i,y_i,c_i)$, $i=1,2,\dots,n$. There are $m$ query operations. In each query, $A,B,C$ are given. You need to find the number of ordered pairs $(i,j)$ such that $Ax_i+By_i+C

The first line contains two integers $n\ m$. The next $n$ lines each contain three integers $x_i\ y_i\ c_i$, $i=1,2,\dots,n$. The next $m$ lines each contain three integers $A\ B\ C$.

Output $m$ lines. Each line contains one integer, the answer to the corresponding query.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078. Sample explanation: The first query corresponds to $(2,2)(3,3)$. The second query corresponds to $(1,1)(2,2)(2,4)(3,3)(3,5)(4,2)(4,4)(5,3)(5,5)$. Constraints: For $5\%$ of the testdata, $n,m\le 10^3$. For another $10\%$ of the testdata, $c_i\le 2$. For another $15\%$ of the testdata, $c_i\le 100$. For another $15\%$ of the testdata, for every $i$, $\max(|x_i|,|y_i|)=10^6$. For another $15\%$ of the testdata, $|A|=|B|=1$. For another $10\%$ of the testdata, $n\le 20000,\;m\le 200000$. For the remaining testdata, there are no special constraints. Each part of the testdata forms a subtask, and the subtasks are independent. All testdata satisfy: $1\le n\le 50000$. $1\le m\le 500000$. $A^2+B^2>0$. $-10^9\le x_i,y_i,A,B,C\le 10^9$. $1\le c_i\le n$. All values are integers. When $i\ne j$, $x_i\ne x_j$ or $y_i\ne y_j$. For all testdata except subtask 4, the $x,y$ coordinates of the $n$ points are chosen uniformly at random within some preset intervals, and it is guaranteed that there are no duplicate points. For the $i$-th point, $c_i$ and $x_i,y_i$ are chosen independently at random, but the distribution of $c_i$ has no special restrictions. Translated by ChatGPT 5