问题 C: 提高生产力
传统题
1.000s
时间限制
256MB
内存限制
12 提交
0 解决
【题目描述】
【题目描述】
Farmer John 有N（1≤N≤2⋅10
5）个农场，编号为1到N。已知 FJ 会在时刻ci关闭农场i。Bessie 在时刻S起床，她希望在农场关闭前访问尽可能多的农场，从而最大限度地提高她这一天的生产力。她计划在时刻ti+S访问农场i。Bessie 必须于严格早于 Farmer John 关闭农场的时刻抵达农场才能成功进行访问。
Bessie 有Q（1≤Q≤2⋅10
5）个询问。对于每个询问，她会给你两个整数S和V。对于每个询问，输出当 Bessie 在时刻S起床是否可以访问至少V个农场。
【输入格式】
输入的第一行包含N和Q。
第二行包含 c1,c2,c3…cN（1≤ci≤10
6）。
第三行包含 t1,t2,t3…tN（1≤ti≤10
6）。
以下Q行，每行包含两个整数V（1≤V≤N）和S（1≤S≤10
6）。
【输出格式】
对Q个询问的每一个输出一行，输出 YES（是）或 NO（否）。
【输入样例】
5 5
3 5 7 9 12
4 2 3 3 8
1 5
1 6
3 3
4 2
5 1
【输出样例】
YES
NO
YES
YES
NO
对于第一个询问，Bessie 将在时间 t=[9,7,8,8,13]访问农场， 因此她在 FJ 关闭农场之前能准时访问到的只有农场4。
对于第二个询问，Bessie 将无法准时访问到任何农场。
对于第三个询问，Bessie 将可以准时访问到农场3,4,5。
对于第四个和第五个询问，Bessie 将能够准时访问除第一个农场之外的所有农场。
【测试点性质】
测试点 2-4：N,Q≤103。
测试点 5-9：ci,ti≤20。
测试点 10-17：没有额外限制。
【输入】
输入的第一行包含N和Q。
第二行包含 c1,c2,c3…cN（1≤ci≤106）。
第三行包含 t1,t2,t3…tN（1≤ti≤106）。
以下Q行，每行包含两个整数V（1≤V≤N）和S（1≤S≤106）。
【输出】
对Q个询问的每一个输出一行，输出 YES（是）或 NO（否）。
【样例输入】复制
5 5
3 5 7 9 12
4 2 3 3 8
1 5
1 6
3 3
4 2
5 1
【样例输出】 复制
YES
NO
YES
YES
NO