AcWing 3263. 买菜
原题链接
简单
作者:
LYMY
,
2024-03-30 10:33:42
,
所有人可见
,
阅读 8
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int a[N],b[N],n,res;
int main()
{
cin>>n;
//本题[s,t]的时间不包括t,所以应该在区间[s,t-1]都加1,当然也可以直接读入2n组数据,
//通过前缀和求出原数组之后,判断值为2的个数,累加即可出答案;
//当然,我们也可以在输入的过程中判断最大的区间右端点,以此来加快遍历过程;
//当然,也可以直接去暴力枚举,两层循环,时间复杂度都是O(10^6)。
int s,t;
for(int i=0;i<n;i++){
scanf("%d%d",&s,&t);
a[s]++,a[t]--;
}
for(int i=1;i<=1000000;i++) a[i]+=a[i-1];
for(int i=0;i<n;i++){
scanf("%d%d",&s,&t);
b[s]++,b[t]--;
}
for(int i=1;i<=1000000;i++) b[i]+=b[i-1];
for(int i=1;i<=1000000;i++)
if(a[i]==1&&b[i]==1) res++;
printf("%d",res);
return 0;
}