首页 > 代码库 > Times[2017-01-25at JiNan]
Times[2017-01-25at JiNan]
Times
【问题描述 】
小 y 作为一名资深的 dotaer，对视野的控制有着深刻的研究。
每个单位在一段特定的时间内会出现在小 y 的视野内，除此之外的时间都在
小 y 看不到的地方。在小 y 看来，视野内的单位数量越多，他就越安全，因为这
意味着有可能藏在阴影中的单位就越少。
现在，小 y 已经知道了每个单位会在什么时候出现在视野内，他想知道，在
一段时间内，总共有多少个单位出现在他的视野内过。
【输入格式】
第一行有两个整数 n，m,表示一共有 n 个单位，而小 y 有 m 个问题。
接下来 n 行，每行两个数 a，b，表示这个单位 a 秒时出现在小 y 的视野内，
出现了 b 秒。
接下来 m 行，每行两个整数 x，y，表示从 x 秒开始，经过 y 秒，其中有多
少个单位出现过。
【输出格式】
m 行，即对于小 y 提出的每个问题的答案。
【输入样例 1】
3 2
2 5
0 10
5 8
0 6
8 2
【输出样例 1】
3
2
【输入样例 2】
1 2
0 10
9 1
10 1
【输出样例 2】
1
0
【数据范围】
30%的数据：
1<=n,m<=1000
100%的数据：
1<=n,m<=200000
1<=x,y,a,b<=maxlongint
/** @Problem: Times* @Author: shenben* @Date: 2017-01-25 20:42:59* @Analyse: (1)如果[a,b)和[c,d)不相交 则①要么b<=c;②要么d<=a (2)对于一个询问区间[c,d) 我们统计对n个已经给出的区间[a,b)出现这两种情况的次数 答案就是n-次数*/#include<cstdio>#include<algorithm>using namespace std;#define O3 __attribute__((optimize("O3")))#define IN inlineO3 IN int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const int N=2e5+5;struct node{ int pos,t,id; node(){} node(int pos,int t,int id):pos(pos),t(t),id(id){} bool operator <(const node &a)const{ return pos==a.pos?t<a.t:pos<a.pos; }}e[N<<2];int n,m,cnt,ans[N],c[4];O3 int main(){ freopen("times.in","r",stdin); freopen("times.out","w",stdout); n=read();m=read(); for(int i=0,x,y;i<n;i++){ x=read();y=read(); e[cnt++]=node(x,1,-1); e[cnt++]=node(x+y,2,-1); } for(int i=0,x,y;i<m;i++){ x=read();y=read(); e[cnt++]=node(x,3,i); e[cnt++]=node(x+y,0,i); } sort(e,e+cnt); for(int i=0;i<cnt;i++){ c[e[i].t]++; if(e[i].t==0) ans[e[i].id]+=c[1]; if(e[i].t==3) ans[e[i].id]-=c[2]; } for(int i=0;i<m;i++) printf("%d\n",ans[i]); return 0;}
Times[2017-01-25at JiNan]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。