Yeah Sure, basically those line are just including the order statistic tree/ordered set, you can check this it out in case you are not much familar with it
https://www.codechef.com/viewsolution/35675507
I have applied binary search too, but not getting the answer.
please have a look.
thank you!!
auto ind = lower_bound(a.begin(),a.end(),val)-a.begin();
if((x+y)==a[0])ind++;
does this work same way as the ordered_set
That would not matterā¦ for N walls a.size. If the last coordinate after the last wall lowerbound will return size+1. (here size =N-1) so the answer would stay correct.
itās matterā¦because if pos==n then a[pos] will throw run time error.
here is the link of your AC submission using vector. CodeChef: Practical coding for everyone
Yeah I just saw what a horrible coincidence is causing the WA. my lowerbound isnāt returning incorrectly but rather the values at that position are matching up which is returning -1
Thanks
a,end() is causing the mess up
Yeah itās O(n).
Right there is a run-time error which is being displayed as WAā¦
Doesnāt codechef have anything to display run-time error? There is SIGSEV and SIGFTPā¦
I can see a RE tag mentioned in the FAQ but I donāt knowā¦
Ya it should ,
this thing messed my whole contest.
Two exactly same code.
1st got WA but 2nd got AC. How is this possible?
I used lower bound and similar solution was uploaded by someone else and i was getting WA but the other solution got AC, can you please help me figure out the difference.
Inside the testcases loop-
// ll is long long.
ll n, i, x;
cin >> n;
vector a;
for (i = 0; i < n; i++)
{
cin >> x;
a.push_back(x);
}
ll q;
cin >> q;
for (i = 0; i < q; i++)
{
ll p, z;
cin >> p >> z;
p += z;
vector::iterator lower;
lower = lower_bound (a.begin(), a.end(), p);
ll cv = lower - a.begin();
if (a[cv] == p)
cout << ā-1ā << endl;
else
cout << cv << endl;
}
Other Soln-
long long int n;
cin>>n;
long long int q[n];
for(long long int i=0;i<n;i++)
{
cin>>q[i];
}
long long int t;
cin>>t;
while(tā)
{
long long int x,y;
cin>>x>>y;
long long int s=x+y;
long long int d = lower_bound(q, q+n, s)-q;
if(q[d]==s)
{
cout<<"-1"<<endl;
continue;
}
else{
cout<<d<<endl;
}
}
I also faced the same issue, I tried both lowerbound as well as Binary search but was getting WA and a very similar soln was accepted
Can you please explain how you solved it with PBDS? I solved it with binary search.
I have used two approach and i think both are correct and same but the first one got WA while the latter one got AC. Here are the links:-
- wrong code- CodeChef: Practical coding for everyone
- correct code -
CodeChef: Practical coding for everyone
Can someone explain why its happening so?
This should not get accepted because lower bound can give n as return value but max array index is n-1 and in the next if statement you are trying to access that element. Which should give runtime error.
Line 27
The same case is withā¦ exactly the same approachā¦ one got WA other got AC
ohh right, Thankyou for helping me, btw this means that both solns shoud not get accepted right??