Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Help in optimizing this cs academy problem .

Revision en1, by atlasworld, 2019-03-06 23:46:02

The problem asks to toggle bits in a certain range that after certain operations all bits becomes 0 .

My O(N2) solution is for a given light bulb if it is on the switch it off and update all the given ranges , but this will be N^2 complexity . How can we reduce it to O(n) . The last lines of the editorial i couldn't understood , how the author is updating the ranges .

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English atlasworld 2019-03-07 00:15:38 308
en4 English atlasworld 2019-03-07 00:14:57 458
en3 English atlasworld 2019-03-06 23:48:42 8 Tiny change: 'bits in a certain range th' -> 'bits in a given range th'
en2 English atlasworld 2019-03-06 23:46:44 21 Tiny change: 'ges . \n\n\n\n' -> 'ges . \n\nhow to do it . ? \n\n\n\n'
en1 English atlasworld 2019-03-06 23:46:02 578 Initial revision (published)