*Official editorial coming soon*

Video link: https://www.youtube.com/watch?v=NctkZHKiPR0

I have just one question. I did exactly whatâ€™s given in the editorial, but I got a lot more wrong answers.

It took me 40 attempts to get AC.

Have i done some implementation mistake?

https://www.codechef.com/viewsolution/30257273

Edit: I just rechecked my program because it should have gotten accepted on first try and realised ans[q] is initialised without inputting q.

Did you submit the same program each time? I thought that the array and the queries were fixed.

Yes, at least 35 of my submissions was this.

Can somebody explain why those â€śsimpleâ€ť solutions work?

It seems that resonse to the queries is never -2.

Why?

I include the proof in the video

Sorry, I am not able to listen to the video.

For K = 10, we went for M/2

Why canâ€™t we do the same for when K = 3? Why go for M-1?

I think you got a little confusedâ€¦ For k=3, 2<=m<=10 which is so small for r-l>=1000 that there is very less probability that maximum height(i.e ans) is less than m-1(maximum possible height). So we are answering the maximum height for every query.

Whereas for k=10, we are questioning taking height of m/2 with x1=l, x2=y(these are the same as query) e.g. if query is from 10 to 200, we ask the same question using x1=10, x2=200 but y=m/2 so that there is maximum probability of hitting maximum segment

Proof of this is explained beautifully in the video.

can someone help with this code? I have used the logic in the video explanation.

codechef.com/viewsolution/30598025

Also when we are trying to query the range sum shouldnâ€™t we reduce the left index by one to make it inclusive of the left and right index? (in the code from given in the description).