Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

compiler01's blog

By compiler01, history, 4 weeks ago, In English,

Hello codedorces

today i was trying to solve problem 920F - SUM and REPLACE , but i failed because of tle

my code works as follow :

first , save locations for every index which have a value a[i] greater than 2 in a set

for every update , find the lower_bound for index l , and upper_bound for index r , and run a for between them , change every number with its number of divisors

for every ans , calculate it by fenwick tree

my code 82714261 failed on test 69 , you may would like to know that i tried with this problem by two data structers ( fenwick tree — sqrt decomposition ) , and both had a tle

can you help ?

thanks in advance

 
 
 
 
  • Vote: I like it
  • -16
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why not do it like the editorial suggests?

Since the updates are 1e5 times, and with every update up to 1e6 elements get updated, you cannot simply do them all.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Kid, don't be depressed. It is very nice to fail on test 69