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
- Found the min distance of the line from the origin which is the length of the normal.
For q queries I checked - Used the equation y=(-x) + c to check if it lies on the line
- 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
@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
can anyone help me why this two condition(1 and 3) are valid??