Light OJ 1088 - Points in Segments Solution

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.

Solution in C++:

///**********ALLAH IS ALMIGHTY************///
///AH Tonmoy
///Department of CSE,23rd batch
///Islamic University,Bangladesh

 #include<bits/stdc++.h>

using namespace std;

int main()

{

    int t,j;

    scanf("%d",&t);

    for(j=1; j<=t; j++)

    {

        printf("Case %d:\n",j);

        int n,p,i,ar;

        scanf("%d %d",&n,&p);

        vector<int>v;

        for(i=1; i<=n; i++)

        {

            scanf("%d", &ar);

            v.push_back(ar);

        }

        sort(v.begin(),v.end());

        for(i=1; i<=p; i++)

        {

            int a,b,ans;

            scanf("%d%d", &a, &b);

            ans=upper_bound(v.begin(),v.end(),b)-lower_bound(v.begin(),v.end(),a);

            printf("%d\n",ans);

        }

    }

    return 0;

}