CLPNT EDITORIAL

Try upper_bound() -1
When you use lower_bound it gives you one greater index of the element lower Or exact. So, if your element is at n-1 position it will return n.
In upper_bound-1.
If index == -1
Cout<< 0
Else if (v[index] == x+y)
Cout<<-1;
Else
Cout<< index+1
You will get correct answer hope you get it :slight_smile:

why WA is coming when used lower_bound function
Please tell where I’m wrong … :pleading_face: :pleading_face:

  1. Found the min distance of the line from the origin which is the length of the normal.
    For q queries I checked
  2. Used the equation y=(-x) + c to check if it lies on the line
  3. Then found the distance of the given point, from origin which I compared to the arr containing distances
#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t>0){
	    t--;
	    int n;
	    cin>>n;
	    vector<long> a;
	    long temp;
	    for(long i =0;i<n;i++){
	        cin>>temp;
	        a.push_back(temp);
	    }
	    //sort(a.begin(),a.end());
	    long q;
	    cin>>q;
	    long ans = 0;
	    long x=0,y=0;
	    auto it = a.begin();
	    for(long i=0;i<q;i++){
	        cin>>x>>y;
	        it = lower_bound(a.begin(),a.end(),x+y);
	        if(*it == x+y)
	            cout<<-1<<endl;
	        else{
	            ans = (it - a.begin());
	            /*
	                  if(it == a.end() || *it < x+y)
	                       ans = n;
	                  if(ans > n)
	                       ans = n;
	                  if(ans < 0 || it == a.begin())
	                       ans = 0;
	           */
	            cout<<ans<<endl;
	        }
	    }
	}
	return 0;
}

I can’t see why i am getting WA here…
help!

https://www.codechef.com/viewsolution/35730710
@faisal1947 Can you help me out with this question, I got the correct answer for the sample test case but when I submitted I got RUNTIME error

I have done similarly. I am still getting TLE. Can anyone please help me?https://www.codechef.com/viewsolution/35732644

hey @tanmayi33 ,
u r getting TLE because u r doing linear inside while(q–) loop:
which makes ur code O(Q*N)
instead make a flag and set it to false,
implement Binary search inside while loop instead of for loop;
if u find a[mid]==x+y then flag=True-> break ->print -1

thankyou bro @mr_bluesky16 got AC.but didn’t got the logic of wrong ac by using lower_bound .as mentioned in the problem a1<a2<a3<…<aN so we can use lower_bound na?? .can u explain

Well as I explained above if you use lower bound it will return n if your element is at n-1 position. So, you can try to use lower_bound() -1 maybe it will work like upper_bound() -1. I told you to use upper_bound() -1 because it always works for me. But i think lower_bound() -1 will also work. But i never tried :sweat_smile:

@mr_bluesky16 but lower bound works like if x+y is present at i=0 it will give 0,if present at n-1,it will give n-1 and if every element is less than x+y in the array then it will give size of array i.e n
so everything seems right
can u give an example where this is going wrong :sneezing_face:

can anyone help me why this two condition(1 and 3) are valid??