# 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.

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.

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