Lightoj 1088 - Points in Segments

Problem link:

Analysis:

Just used lower_bound  and upper_bound functions which we all know uses built in binary search function. so for any aray of points like
 a[10] =  {1, 2, 4, 5, 5, 5, 6, 7, 8, 8}
lower_bound(1) = 0              upper_bound(1) = 1        
lower_bound(2) = 1              upper_bound(2) = 2
lower_bound(4) = 2              upper_bound(4) = 3
lower_bound(8) = 8              upper_bound(8) = 10
lower_bound(-500) = 0        upper_bound(10000) = 10
using those you can see lower and upper bound works. than just we find lower bound for left of the segment and upper bound for the right limit of the segment and the difference is our answer.

Here goes the code:

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main(){
4.     int ts;
5.     scanf("%d", &ts);
6.     for(int p = 1; p <= ts; p++){
7.         printf("Case %d:\n", p);
8.     vector<int>v;
9.     int n, q;
10.     scanf("%d%d", &n, &q);
11.     for(int i = 0; i <n; i++){
12.         int a;
13.         scanf("%d", &a);
14.         v.push_back(a);
15.     }
16.     sort(v.begin(), v.end());
17.     for(int i = 0; i <q; i++){
18.             int l, r;
19.             scanf("%d%d", &l , &r);
20.             printf("%d\n", upper_bound(v.begin(), v.end(),r)-lower_bound(v.begin(), v.end(),l));
21.     }
22.     }
23.     return 0;
24. }