Flowers
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2579 Accepted Submission(s): 1265
Problem Description
As
is known to all, the blooming time and duration varies between
different kinds of flowers. Now there is a garden planted full of
flowers. The gardener wants to know how many flowers will bloom in the
garden in a specific time. But there are too many flowers in the garden,
so he wants you to help him.
is known to all, the blooming time and duration varies between
different kinds of flowers. Now there is a garden planted full of
flowers. The gardener wants to know how many flowers will bloom in the
garden in a specific time. But there are too many flowers in the garden,
so he wants you to help him.
Input
The first line contains a single integer t (1 <= t <= 10), the number of test cases.
For
each case, the first line contains two integer N and M, where N (1
<= N <= 10^5) is the number of flowers, and M (1 <= M <=
10^5) is the query times.
In the next N lines, each line contains two integer Si and Ti (1 <= Si <= Ti <= 10^9), means i-th flower will be blooming at time [Si, Ti].
In the next M lines, each line contains an integer Ti, means the time of i-th query.
For
each case, the first line contains two integer N and M, where N (1
<= N <= 10^5) is the number of flowers, and M (1 <= M <=
10^5) is the query times.
In the next N lines, each line contains two integer Si and Ti (1 <= Si <= Ti <= 10^9), means i-th flower will be blooming at time [Si, Ti].
In the next M lines, each line contains an integer Ti, means the time of i-th query.
Output
For
each case, output the case number as shown and then print M lines. Each
line contains an integer, meaning the number of blooming flowers.
Sample outputs are available for more details.
each case, output the case number as shown and then print M lines. Each
line contains an integer, meaning the number of blooming flowers.
Sample outputs are available for more details.
Sample Input
2
1 1
5 10
4
2 3
1 4
4 8
1
4
6
1 1
5 10
4
2 3
1 4
4 8
1
4
6
Sample Output
Case #1:
0
Case #2:
1
2
1
0
Case #2:
1
2
1
题解：类似颜色段那题，突发奇想，二分搞了搞，upper，lower那错了半天，想了一组数据才发现问题；
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const double PI=acos(-);
#define mem(x,y) memset(x,y,sizeof(x))
const int MAXN=1e5+;
int s[MAXN],e[MAXN];
int main(){
int t,M,N,flot=;
scanf("%d",&t);
while(t--){
scanf("%d%d",&N,&M);
for(int i=;i<N;i++){
scanf("%d%d",&s[i],&e[i]);
}
sort(s,s+N);sort(e,e+N);
int q;
printf("Case #%d:\n",++flot);
// for(int i=0;i<N;i++)printf("%d ",s[i]);puts("");
// for(int i=0;i<N;i++)printf("%d ",e[i]);puts("");
while(M--){
scanf("%d",&q);
int x=upper_bound(s,s+N,q)-s;
int y=lower_bound(e,e+N,q)-e;
//printf("%d %d\n",x,y);
// if(e[y-1]==q)y--;
// if(s[x]==q)x++;
printf("%d\n",x-y);
}
}
return ;
}