3841. [JOISC 2019 Day1] 考试

【题目描述】

有 $N$ 名学生参加了一个考试，考试包括数学和信息学两个科目。第 $i$ 名学生在数学中获得了 $S_i$ 分，在信息学中获得了 $T_i$ 分。$T$ 教授和 $I$ 教授将根据每名学生的得分决定是否挂他们的科。

   $T$ 教授认为两门科目的得分都很重要，他认为只有数学考了至少 $A$ 分，且信息学考了至少 $B$ 分的学生可以通过考试。

   $I$ 教授认为只有总得分才是重要的，他认为两门科目的总得分至少为 $C$ 分的学生可以通过考试。

   只有按两名教授的标准都通过的学生才真的不会挂科。

现在给出 $Q$ 组询问，每组询问的内容是，给定一个三元组 $(X_j, Y_j, Z_j)$，当 $A=X_j, B=Y_j, C=Z_j$ 时有多少学生能不挂科，你需要对每一组询问分别进行回答。

【输入格式】

第一行包括两个整数 $N, Q$，表示学生人数和询问个数。

接下来 $N$ 行，第 $i$ 行两个整数 $S_i$ 和 $T_i$，表示第 $i$ 名学生的分数。

接下来 $Q$ 行，第 $i$ 行三个整数 $X_i, Y_i, Z_i$，表示一组询问。

【输出格式】

输出 $Q$ 行，每行一个整数，表示询问的答案（即有多少学生不挂科）。

【样例1输入】

5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100

【样例1输出】

2
4
1
1

【样例1说明】

当 $A=20, B=50, C=120$ 时，只有第一名和第二名学生能通过考试，因此答案为 $2$。

当 $A=10, B=10, C=100$ 时，只有第一、二、四、五名学生能通过考试，因此答案为 $4$。

当 $A=60, B=60, C=80$ 时，只有第二名学生能通过考试，因此答案为 $1$。

当 $A=0, B=100, C=100$ 时，只有第一名学生能通过考试，因此答案为 $1$。

【样例2输入】

10 10
41304 98327
91921 28251
85635 59191
30361 72671
28949 96958
99041 37826
10245 2726
19387 20282
60366 87723
95388 49726
52302 69501 66009
43754 45346 3158
25224 58881 18727
7298 24412 63782
24107 10583 61508
65025 29140 7278
36104 56758 2775
23126 67608 122051
56910 17272 62933
39675 15874 117117

【样例2输出】

1
3
5
8
8
3
3
3
5
6

【样例3/4/5】

点击下载样例3/4/5

【数据规模与约定】

对于测试点 $1 \sim 3$：$N,Q \le 3000$;

对于测试点 $4 \sim 6$：$S_i, T_i \le 10^5, X_j, Y_j \le 10^5, Z_j=0$;

对于测试点 $7 \sim 9$：$S_i, T_i \le 10^5, X_j, Y_j \le 10^5, Z_j \le 2 \times 10^5$;

对于所有输入数据：

$1 \le N, Q \le 100 000, 0 \le S_i, T_i \le 10^9 (1 \le i \le N)$,

$0 \le X_j, Y_j \le 10^9 (1 \le j \le Q), 0 \le Z_j \le 2 \times 10^9 (1 \le j \le Q)$。

【来源】

题目译自 $JOISC\ 2019\ Day1\ T1$「試験 / $Examination$」

https://loj.ac/p/3030