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 */