花莲县网站建设_网站建设公司_Python_seo优化

P2650 弹幕考察

题目背景

zeromaker 是个手残，但是他喜欢玩东方 project，ex 什么的最喜欢了

题目描述

zeromaker 对弹幕的视野控制有着深刻的研究。 每个弹幕在一段特定的时间内会出现在 zeromaker 的视野内，除此之外的时间都在 zeromaker 看不到的地方。在 zeromaker 看来，视野内的弹幕数量越多，图就越难，因为这意味着 @#￥%。 现在，zeromaker 想要评测这张图的难度，他已经知道了每个弹幕会在什么时候出现在视野内，他想知道，在一段时间内，总共有多少个弹幕出现在他的视野内过。

输入格式

第一行有两个整数nnn，mmm,表示一共有nnn个弹幕，而 zeromaker 有mmm个问题。

接下来nnn行，每行两个数aaa，bbb，表示这个弹幕aaa秒时出现在 zeromaker 的视野内，出现了bbb秒。 接下来mmm行，每行两个整数xxx，yyy，表示从xxx秒开始，经过yyy秒，其中有多少个弹幕出现过。

注意：此处的“秒”为时刻，弹幕在视野出现过当且仅当视野观测与弹幕出现的时间间隔存在重合，仅端点重合（如弹幕在第222秒结束的同时观测从第222秒开始）不算在视野出现。

输出格式

mmm行，即对于 zeromaker 提出的每个问题的答案。

输入输出样例 #1

输入 #1

3 2 2 5 0 10 5 8 0 6 8 2

输出 #1

3 2

输入输出样例 #2

输入 #2

1 2 0 10 9 1 10 1

输出 #2

1 0

说明/提示

样例1说明：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 弹幕1 |--------------| 弹幕2 |-----------------------------| 弹幕3 |-----------------------| 视野1 |-----------------| 视野2 |-----|

样例2说明：

0 1 2 3 4 5 6 7 8 9 10 11 弹幕1 |-----------------------------| 视野1 |--| 视野2 |--|

• 30%30\%30%的数据：n,m≤103n,m \le 10^3n,m≤103。
• 100%100\%100%的数据：1≤n,m≤1051 \le n,m \le 10^51≤n,m≤105，0≤x,y,a,b≤231−10 \le x,y,a,b \le 2^{31}-10≤x,y,a,b≤231−1。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;inti,n,m,l[N],le,r[N],x,y;intmain(){cin>>n>>m;for(i=1;i<=n;i++){cin>>l[i]>>le;r[i]=l[i]+le-1;}sort(l+1,l+n+1);sort(r+1,r+n+1);while(m--){cin>>x>>le;y=x+le;cout<<(lower_bound(l+1,l+n+1,y)-l)-(lower_bound(r+1,r+n+1,x)-r)<<"\n";}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容