https://www.youtube.com/watch?v=0rCFkuQS968
Found an MIT lecture on this. Complexity: { O(N) (update),O(1) (query) }
https://www.youtube.com/watch?v=0rCFkuQS968
Found an MIT lecture on this. Complexity: { O(N) (update),O(1) (query) }
i used segment tree to solve this question but in last two test cases i am getting runtime error can anyone explain me why i am getting runtime error link text
i think so my solution is well optimized and i donāt know for which test cases i am getting runtime error if i increased the size of array around 10^7 then i am getting tle please anyone explain me why i am getting runtime error and tle if i increase the size of array?
Anybody solved this problem with BIT ?
I solved the problem using segment tree which takes O(logn) time.I got only 70 points,for the last sub-task I am getting a TLE.Can someone please help me?
solution- CodeChef: Practical coding for everyone
Any help is appreciated.
Read about cache
It have been fixed now; when edotorial was published, there was āWe can use Splay Tree to solve this case.ā in case 3.
Ok, thank you.
On the other hand, such āworthless optimizationā may give you one more solved problem at regional contest or even world finals. For me it happened 10-15 times during trainings already. I donāt think that this problem is good, for me picking such constants looks like easy way to make problem āharderā and simply get more money for it But people who canāt solve a problem - donāt deserve higher rankings.
order of 10^8 operations per second is a good approximation on an upper bound.
thanks, upper bound for codechef increased,
but i feel its risky in competitions where you can make one submission or you get penalty for wrong one.
Can you give the link to tutorial of sparse table
just by changing a[n][logn] to a[logn][n] the solution gets passedā¦ It doesnāt make any sense for us to spend hours on end to think of such optimizationsā¦ a constraint of m<=10^7 would have easily sufficed in this problem -_-
thatās sweet, thanks
Use normal sparse[N][logN] ,no need to use sparse[logN][N] .Precompute all log2 value and stop using useless mod task , use this if l>=n-1 l%=n-1ā¦You will get full points .