CLPNT EDITORIAL

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

1 Like

https://www.codechef.com/viewsolution/35675507
I have applied binary search too, but not getting the answer.
please have a look.

thank you!!

this might help:CodeChef: Practical coding for everyone

        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

1 Like

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.

  1. CodeChef: Practical coding for everyone
  2. CodeChef: Practical coding for everyone

1st got WA but 2nd got AC. How is this possible?

1 Like

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:-

  1. wrong code- CodeChef: Practical coding for everyone
  2. 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.

1 Like

Line 27

1 Like

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??