LightOj 1088 (Points in Segments)

#lightoj #cp #problem_solving #binary_search

Idea

Binary Search

  • Within time complexity only thing to do is binary search i.e use the lower_bound or the upper bound function to find the value of the index .
  • lower_bound : points to the first number equals to the ‘num’ or greater than the ‘num’
  • upper_bound : points to the first number greater than the ‘num’

Critical Test Cases (Queries) :
6(present) 10(present) –> r-l+1
5(absent) 10(present) –> r-l+1
5(absent) 9(absent) –> r-l
6(present) 9(absent) –> r-l 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

/* Which of the favors of your Lord will you deny? */

#include<bits/stdc++.h>
using namespace std;

#define pi       acos(-1)

#define SI(n)    scanf("%d",&n)
#define SLL(n)   scanf("%lld",&n)
#define SULL(n)  scanf("%llu",&n)
#define SC(n)    scanf("%c",&n)
#define SD(n)    scanf("%lf",&n)

#define fr(i,a,b) for(int i=a ,_b=(b) ;i<= _b;i++)

#define LL      long long
#define PUB     push_back
#define POB     pop_back
#define MP      make_pair
#define PII     pair<int,int>
#define PLL     pair<ll,ll>

#define GCD     __gcd
#define DEBUG   cout<<"aw"<<endl;

int ara[100010];

int main()
{
    int tc;
    SI(tc);

    fr(i,1,tc)
    {
        int n,q,a,b,ans;
        SI(n),SI(q);

        fill(ara+1,ara+n+1,0);

        fr(j,0,n-1)
            SI(ara[j]);

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

        fr(k,1,q)
        {
            SI(a),SI(b);
            int left = lower_bound(ara,ara+n,a)-ara;
            int right = lower_bound(ara,ara+n,b)-ara;

            //cout<<"**"<<left<<" "<<right<<endl;

            if(binary_search(ara,ara+n,b)==true)
                ans = right - left + 1;
            else // binary_search(b)==false
                ans = right - left;

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

        }

    }

    return 0;
}