CHANOQ - Editorial

I didnt even thpught much on the question. I just got the gist of it to submit brute force. I will think of the Q when I upsolve, and till then I cant help you here, so didnt reply.

Actually rules says you should reply to geneuine queries gor first 9-10 days of publishing editorial.

I guess segment trees/sqrt decomposition will be required for the query in any way.

Dont use the pointers (* operator for value referencing), instead use only arrays (see the tester’s code for implementation details). Or, you can also using segment trees instead of persistent segment tree.

@lovemaydie How did you do preprocessing of points to decide which intervals a point belong ?

@vivek_shah98 Your solution has a complexity O(n * q) which will give a TLE. We perform your solution only for q1 fraction of total queries q whose number of points are greater then parameter S given in above solution. Sum of m over all queries is O(n), so O(q1 * S) = O(n) which gives q1 as O(sqrt(n * log(n))). So complexity of your solution for fraction of queries will be O(q1 * n) = O(n * sqrt(n * log(n))). For other fraction of queries we cannot upperbound their count.

@jh0n_12358 I posted a comment for clarification, but codechef removes all the newlines, spaces and tab indentations.
So please look at the screenshot here