Danny_Phantom's blog

TLE USING MO'S
By Danny_Phantom, history, 2 years ago, In English

i was trying to solve https://mirror.codeforces.com/problemset/problem/221/D using mo's but i was getting tle so can someone help how can i optimize this code my submissions https://mirror.codeforces.com/contest/221/submission/183198017 update 1:https://mirror.codeforces.com/contest/221/submission/183252354 accepted answer update : can someone explain why i got tle using c++20 but acc using c++17!

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

Comments Comments (1)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use coordinate compression. Make a copy of array a, let's call it d, sort it, delete all unique elements, and make every element in a equal to the index of that element in sorted array(you can use std::lower_bound).

Now you have number <= 1e5, you can make an array instead of map, and avoid additional log (don't forget that you need to do occurences[x] == d[x] now)

→ Reply