首页 > 代码库 > Times[2017-01-25at JiNan]

Times[2017-01-25at JiNan]

2024-09-04 00:13:10   222人阅读

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]


联系
我们