注册深圳公司,网站做优化有用吗,网站制作公,比较好的网站公司最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。
具体来时#xff0c;如果在 t t t 时刻做了核酸检测#xff0c;则经过一段时间后可以得到核酸检测阴性证明。
这里我们假定等待核酸检测结果需要 k k k 个单位时间#xff0c;即在 t k tk tk 时刻…最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。
具体来时如果在 t t t 时刻做了核酸检测则经过一段时间后可以得到核酸检测阴性证明。
这里我们假定等待核酸检测结果需要 k k k 个单位时间即在 t k tk tk 时刻可以获得结果。
如果一个场所要求持 24 24 24 个单位时间内核酸检测结果入内那么凭上述的核酸检测结果可以在第 t k tk tk 时刻到第 t k 23 tk23 tk23 时刻进入该场所。
小 C C C 按时间顺序列出接下来的 n n n 项出行计划其中第 i i i 项 1 ≤ i ≤ n 1≤i≤n 1≤i≤n可以概括为 t i t_i ti 时刻进入某场所该场所需持有 c i c_i ci 个单位时间内的核酸检测结果入内其中 0 c i ≤ 2 × 1 0 5 0c_i≤2×10^5 0ci≤2×105 。
为了合理安排核酸检测时间试根据小 C C C 的出行计划回答如下查询
如果在 q q q 时刻做了核酸检测有多少项出行计划的核酸检测要求可以得到满足这样的查询共有 m m m 个分别为 q 1 , q 2 , ⋯ , q m q_1,q_2,⋯,q_m q1,q2,⋯,qm 查询之间互不影响。
输入格式 输入的第一行包含空格分隔的三个正整数 n n n 、 m m m 和 k k k 分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。
接下来输入 n n n 行其中每行包含用空格分隔的两个正整数 t i t_i ti 、 c i c_i ci 表示一项出行计划出行计划按时间顺序给出满足 0 t 1 ≤ t 2 ≤ ⋯ ≤ t n ≤ 2 × 1 0 5 0t_1≤t_2≤⋯≤t_n≤2×10^5 0t1≤t2≤⋯≤tn≤2×105 。
最后输入 m m m 行每行仅包含一个正整数 qi 表示一个查询。 m m m 个查询亦按照时间顺序给出满足 0 q 1 q 2 ⋯ q m ≤ 2 × 1 0 5 0q^1q^2⋯q^m≤2×10^5 0q1q2⋯qm≤2×105 。
输出格式 输出共 m m m 行每行一个整数表示对应查询的答案。
数据范围 40 % 40\% 40% 的测试数据满足 0 n , k ≤ 1000 、 m 1 0n,k≤1000、m1 0n,k≤1000、m1 70 % 70\% 70% 的测试数据满足 0 n , m , k ≤ 1000 0n,m,k≤1000 0n,m,k≤1000 全部的测试数据满足 0 n , m , k ≤ 1 0 5 0n,m,k≤10^5 0n,m,k≤105。
输入样例
6 2 10
5 24
10 24
11 24
34 24
35 24
35 48
1
2输出样例
3
3样例解释 时刻 1 1 1 做检测可以满足第三、四、六项出行计划 时刻 2 2 2 做检测可以满足第四、五、六项出行计划。 思路
对于某个场所只有当出行时刻满足 q k t i q k c i − 1 qk t_i qkc_i-1 qktiqkci−1 时这些出行时刻才会算数这个式子可以转换为 t i − c i − k 1 q t i − k t_i-c_i-k1 q t_i - k ti−ci−k1qti−k即可以看作对每个 q q q 求有多少个 i i i 满足这个性质转换为对于当前 q q q求它覆盖了多少个这样的区间用差分可以解决。
#includeiostreamusing namespace std;const int N 200010;int d[N];int main(){int n, m, k;scanf(%d%d%d, n, m, k);int t, c;for(int i 0; i n; i){scanf(%d%d, t, c);int l t-c-k1, r t-k;if(r 0) d[max(l, 0)], d[r1]--;}for(int i 1; i N; i) d[i] d[i-1];int q;for(int i 0; i m; i){scanf(%d, q);printf(%d\n, d[q]);}return 0;
}
