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
I have applied binary search too, but not getting the answer.
please have a look.
this might help:CodeChef: Practical coding for everyone
auto ind = lower_bound(a.begin(),a.end(),val)-a.begin(); if((x+y)==a)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
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;
for (i = 0; i < n; i++)
cin >> x;
cin >> q;
for (i = 0; i < q; i++)
ll p, z;
cin >> p >> z;
p += z;
lower = lower_bound (a.begin(), a.end(), p);
ll cv = lower - a.begin();
if (a[cv] == p)
cout << “-1” << endl;
cout << cv << endl;
long long int n;
long long int q[n];
for(long long int i=0;i<n;i++)
long long int t;
long long int x,y;
long long int s=x+y;
long long int d = lower_bound(q, q+n, s)-q;
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:-
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.
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??