QOJ.ac

QOJ

Time Limit: 12 s Memory Limit: 512 MB Total points: 100

# 4409. 袜子

统计

题目描述

给定 $n$ 个点 $(x_i,y_i,c_i)$,$i=1,2,\dots,n$,共有 $m$ 次查询操作,每次查询给定 $A,B,C$,问满足 $Ax_i+By_i+C < 0$,$Ax_j+By_j+C < 0$,$c_i=c_j$ 的二元组 $(i,j)$ 的个数。

输入格式

第一行两个整数 $n\ m$;

接下来 $n$ 行,每行三个整数 $x_i\ y_i\ c_i$,$i=1,2,\dots,n$;

接下来 $m$ 行,每行三个整数 $A\ B\ C$。

输出格式

共 $m$ 行,每行一个整数,表示答案。

样例数据

样例输入

5 2
2 -1 1
0 -3 5
1 -3 2
1 3 5
3 2 2
1 2 4
1 -2 -9

样例输出

2
9

样例解释:

第一个查询对应 $(2,2)(3,3)$;

第二个查询对应 $(1,1)(2,2)(2,4)(3,3)(3,5)(4,2)(4,4)(5,3)(5,5)$。

子任务

对 $5\%$ 的数据,$n,m\le 10^3$;

对另外 $10\%$ 的数据,$c_i\le 2$;

对另外 $15\%$ 的数据,$c_i\le 100$;

对另外 $15\%$ 的数据,$\max(|x_i|,|y_i|)=10^6$;

对另外 $15\%$ 的数据,$|A|=|B|=1$;

对另外 $10\%$ 的数据,$n\le 20000,\;m\le 200000$;

对于其余数据,无特殊约束。

每部分数据构成子任务,无依赖关系。

所有数据满足:

$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$;

所有数值为整数;

当 $i\ne j$ 时,$x_i\ne y_i$ 或 $x_j\ne y_j$。

对于除了子任务 4 以外的数据,满足 $n$ 个点的 $x,y$ 坐标分别在某个预设的区间内均匀随机选取,并保证没有重复的点,且对于第 $i$ 个点,$c_i$ 和 $x_i,y_i$ 是分别独立地随机选取的,但 $c_i$ 的分布没有特殊限制。