Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

ibrahimsherif's blog

By ibrahimsherif, history, 8 months ago, In English,

http://acm.timus.ru/problem.aspx?space=1&num=1613

Hi, i am trying to solve this problem using SQRT decomposition but i am getting TLE, how can it be optimized more or is my approach wrong.

Here is my code: https://ideone.com/tnuvKA

 
 
 
 
  • Vote: I like it  
  • +10
  • Vote: I do not like it  

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you got TLE because you were doing binary search on each block. You can speed it up by using MO's Algorithm + Compression.