ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1846. GCD 2010

Is O (N log N) the only viable solution ?
Posted by shashwat 20 Mar 2014 14:05
Is it possible to solve this problem using SQRT-decomposition ?
0.5 second is a very tight limit and in-spite of minor optimizations and fast I/O my code having complexity of O (N * sqrt (N)) is getting TLE on test case 17.  I am just curious about the possibility.
Re: Is O (N log N) the only viable solution ?
Posted by mikroz 4 Jul 2014 06:48
It is actually a very tough problem when you're using a segments tree, so I do not think that using a SQRT-decomposition is a very good idea. For me the key was to implement the segments tree with iterative update procedure.