Flowers
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2585 Accepted Submission(s): 1271
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.
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.
Sample outputs are available for more details.
Sample Input
2 1 1 5 10 4 2 3 1 4 4 8 1 4 6
Sample Output
Case #1: 0 Case #2: 1 2 1
Author
BJTU
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAX 100000 struct tree { int l,r; int m; }num[MAX*10]; void build(int node,int l,int r) { num[node].l=l; num[node].r=r; num[node].m=0; if(l==r) return ; int mid=(l+r)/2; build(node*2,l,mid); build(node*2+1,mid+1,r); } void updata(int node,int l,int r) { if(num[node].l==l&&num[node].r==r) { num[node].m++; return ; } int mid=(num[node].l+num[node].r)/2; if(r<=mid) updata(node*2,l,r); else if(l>mid) updata(node*2+1,l,r); else { updata(node*2,l,mid); updata(node*2+1,mid+1,r); } } int query(int node,int l,int r) { if(num[node].l==l&&num[node].r==r) { return num[node].m; } int mid=(num[node].l+num[node].r)/2; if(r<=mid) return query(node*2,l,r)+num[node].m; else { if(l>mid) return query(node*2+1,l,r)+num[node].m; else return query(node*2,l,mid)+query(node*2+1,mid+1,r); } } int main() { int t; int Case=1; scanf("%d",&t); while(t--) { int m,n,x,y,z; scanf("%d%d",&n,&m); build(1,1,MAX); while(n--) { scanf("%d%d",&x,&y); updata(1,x,y); } printf("Case #%d: ",Case++); while(m--) { scanf("%d",&z); printf("%d ",query(1,z,z)); } } return 0; } 醉了醉了,二分都可以 <pre name="code" class="cpp">#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAX 100010 int a[MAX],b[MAX]; int main() { int t; int Case=1; scanf("%d",&t); while(t--) { int m,n,x,y,z; scanf("%d%d",&n,&m); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=0;i<n;i++) scanf("%d%d",&a[i],&b[i]); sort(a,a+n);sort(b,b+n); printf("Case #%d: ",Case++); for(int i=0;i<m;i++) { scanf("%d",&z); x=upper_bound(a,a+n,z)-a; y=lower_bound(b,b+n,z)-b; printf("%d ",x-y); } } return 0; }