#PU1397. USACO 2024 February Contest, Bronze — Problem 3. Maximizing Productivity

    ID: 1414 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:feb24来源:usaco.orgscoring:equal_test_cases枚举二分答案

USACO 2024 February Contest, Bronze — Problem 3. Maximizing Productivity

USACO 2024 February Contest, Bronze — Problem 3. Maximizing Productivity

题目描述

Farmer John has NN (1≤N≤2⋅1051 \leq N \leq 2 \cdot 10^5) farms, numbered from 11 to NN. It is known that FJ closes farm ii at time cic_i. Bessie wakes up at time SS, and wants to maximize the productivity of her day by visiting as many farms as possible before they close. She plans to visit farm ii on time ti+St_i + S. Bessie must arrive at a farm strictly before Farmer John closes it to actually visit it. Bessie has QQ (1≤Q≤2⋅105)(1 \leq Q \leq 2 \cdot 10^5) queries. For each query, she gives you two integers SS and VV. For each query, output whether Bessie can visit at least VV farms if she wakes up at time SS.

输入格式

The first line consists of NN and QQ. The second line consists of c1,c2,c3…cNc_1, c_2, c_3 \dots c_N (1≤ci≤1061 \leq c_i \leq 10^6). The third line consists of t1,t2,t3…tNt_1, t_2, t_3 \dots t_N (1≤ti≤1061 \leq t_i \leq 10^6). The next QQ lines each consist of two integers VV (1≤V≤N1 \leq V \leq N) and SS (1≤S≤1061 \leq S \leq 10^6).

输出格式

For each of the QQ queries, output YES or NO on a new line.

数据范围

Inputs 2-4: N,Q≤103N,Q\le 10^3 Inputs 5-9: ci,ti≤20c_i, t_i \le 20 Inputs 10-17: No additional constraints. Problem credits: Chongtian Ma

样例

样例 1

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
For the first query, Bessie will visit the farms at time $t = [9, 7, 8, 8, 13]$,
so she will only get to visit farm $4$ on time before FJ closes the farm.
For the second query, Bessie will not be able to visit any of the farms on time.
For the third query, Bessie will visit farms $3, 4, 5$ on time.
For the fourth and fifth queries, Bessie will be able to visit all but the first
farm on time.