1088 – Points in Segments

Problem Link

Solution

 

#include <bits/stdc++.h>
int ar[100005],n;
using namespace std;
int lbs(int target,int n)
{
int low=0,high=n,mid;
while(low<=high)
{
mid=(low+high)>>1;
if(ar[mid]==target)
{
return mid;
// if(ar[mid-1]==target) high=mid-1;

}
else if(ar[mid]>target) high=mid-1;
else low=mid+1;
}

return low;
}

int hbs(int target,int n)
{
int low=0,high=n,mid;
while(low<=high)
{
mid=(low+high)>>1;
if(ar[mid]==target)
{
return mid;
// if(ar[mid+1]==target) low=mid+1;

}
else if(ar[mid]>target) high=mid-1;
else low=mid+1;
}

return high;
}

int main()
{
int t;

scanf(“%d”,&t);
for(int cs=1; cs<=t; cs++)
{
int n,q;
scanf(“%d %d”,&n,&q);
for(int i=0; i<n; i++) scanf(“%d”,ar+i);
printf(“Case %d:\n”,cs);
while(q–)
{
int low,high;
scanf(“%d %d”,&low,&high);
int l=lbs(low,n-1);
int h=hbs(high,n-1);
// cout<<h<<l<<endl;
printf(“%d\n”,(h-l)+1);

}
}
return 0;
}

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s