Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long int
- #define rep(i,n) for(i=0;i<n;i++)
- long long int ar1[100000],ar2[100000];
- struct valpos
- {
- long long int val,pos;
- };
- ll find_low(ll ar[], ll given, ll siz)
- {
- ll posmid = siz/2;
- ll mid = ar[posmid];
- //valpos ret;
- while(1)
- {
- //cout<<mid<<"*\n";
- if(mid<given)
- {
- if(posmid == siz - 1)
- {
- return -1;
- }
- else
- {
- posmid = posmid + (siz - posmid)/2;
- mid = ar[posmid];
- }
- }
- else if(mid == given)
- {
- return posmid;
- }
- else if(mid>given)
- {
- if(posmid==0)
- {
- return posmid;
- }
- else if(ar[posmid - 1]<given)
- {
- return posmid;
- }
- else if(ar[posmid - 1]==given)
- {
- return posmid - 1;
- }
- else
- {
- posmid = posmid/2;
- mid = ar[posmid];
- }
- }
- }
- }
- ll find_high(ll ar[], ll given, ll siz)
- {
- ll posmid = siz/2;
- ll mid = ar[posmid];
- //valpos ret;
- while(1)
- {
- //cout<<mid<<"**\n";
- if(mid>given)
- {
- if(posmid == 0)
- {
- return -1;
- }
- else
- {
- posmid = posmid/2;
- mid = ar[posmid];
- }
- }
- else if(mid == given)
- {
- return posmid;
- }
- else if(mid<given)
- {
- if(posmid == siz-1)
- {
- return posmid;
- }
- else if(ar[posmid + 1]>given)
- {
- return posmid;
- }
- else if(ar[posmid + 1]==given)
- {
- return posmid + 1;
- }
- else
- {
- posmid = posmid +(siz-posmid)/2;
- mid = ar[posmid];
- }
- }
- }
- }
- int main()
- {
- int t;
- cin>>t;
- ll i,j,k,posl,posh;
- for(i=0;i<t;i++)
- {
- ll n,q;
- cin>>n>>q;
- cout<<"Case "<<i+1<<":"<<"\n";
- for(j = 0;j<n;j++)
- {
- cin>>ar1[j];
- }
- for(j = 0;j<q;j++)
- {
- ll sl,sh;
- cin>>sl>>sh;
- posl = find_low(ar1,sl,n);
- if(posl==-1)
- {
- cout<<"0\n";
- }
- else
- {
- posh = find_high(ar1,sh,n);
- if(posh==-1)
- {
- cout<<n-1-posl+1<<"\n";
- }
- else
- {
- cout<<posh-posl+1 <<"\n";
- }
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement