Problem Name :  Points in Segments

Problem Link : See Problem : LightOJ 1088

Its also a Binary Search related Problem…
You have to find lower bound and upper bound index from  given array.
Then Subtract Upper to lower bound index.
Note : Use Scanf() and Printf() Function , cin/cout causes TLE 😛

Solution  :

#include<bits/stdc++.h>
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
#define rep(i,n) for(int i=1;i<=n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
 
typedef long long LL;
 
using namespace std;
 
int main()
{
    //read;
    //write;
    LL l, n, x, q, N, M, I1, I2, t, tc = 0;
    scanf("%lld",&t);
    
    while(t--)
    {
        
    LL a[100005];

    scanf("%lld%lld",&n,&q);
    rep(i,n){scanf("%lld",&a[i]);}
    printf("Case %lld:\n",++tc);

    rep(i,q)
    {
        scanf("%lld%lld",&N,&M);
        LL low = 1, up = n, mid, Low, Up;
        while(low<=up)
        {
            mid = (low+up)/2;
            if(a[mid]==N){low = mid; break;}
            else if(a[mid]<N){low = mid + 1;}
            else{up = mid - 1;}
        }
        Low = low;
        low = 1, up = n, mid = 0;
        while(low<=up)
        {
            mid = (low+up)/2;
            if(a[mid]<=M){low = mid + 1;}
            else{up = mid - 1;}
        }
        Up = low;
        //cout<<Up<<" "<<Low<<endl;
        printf("%lld\n",Up-Low);
    }
    }
    return 0;
}
/*
1
5 3
1 4 6 8 10
0 5
6 10
7 100000
*/
Advertisements