#3030. 「JOISC 2019 Day1」考试

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WAAutoMaton

题目描述

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

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

数据范围与提示

Subtask # 分值 数据规模
1 2 N,Q \le 3000
2 20 S_i, T_i \le 10^5, X_j, Y_j \le 10^5, Z_j=0
3 21 S_i, T_i \le 10^5, X_j, Y_j \le 10^5, Z_j \le 2 \times 10^5
4 57 无特殊限制

对于所有输入数据,有 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)