SPOJ COT

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
islamdiaa
New poster
Posts: 1
Joined: Thu Aug 23, 2012 3:59 pm

SPOJ COT

Post by islamdiaa » Thu Aug 23, 2012 4:01 pm

http://www.spoj.pl/problems/COT/

I can't come to an efficient algorithm to this problem except O( M log ^3 N ) using binary search + segment tree + heavy light decomposition. There is an ( M log ^ 2 N) solution which will TLE. The intended one is O(M log N) solution, can anyone please explain any of them? Thanks in advance :)

Post Reply

Return to “Algorithms”