simp_pro's blog

[HELP] What is the memory limit of my code
By simp_pro, history, 5 months ago, In English

What is the memory limit of my code : https://codeforces.com/contest/1706/submission/237628836

vector a,r : 2*8MB = 16MB

In vector<vector> change, I am pushing a new element only if a previous element is removed. It ensures that number of integers inside this change 2d vector is exactly n at all times. So it should be 8MB(for integers) + 8MB(for each vector)

Overall, it should be 32 MB only. However, it is exceeding 64 MB and giving help

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

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

Auto comment: topic has been updated by simp_pro (previous revision, new revision, compare).

→ Reply
»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

std::vector doesn't free the allocated space when calling pop_back(): https://stackoverflow.com/questions/1536753/does-stdvector-pop-back-change-vectors-capacity

You can reduce capacity with vector::shrink_to_fit(), but that is $$$O(\mathrm{size})$$$ which isn't fast enough (237641351).

Instead, you can use a linked list (std::list). It is significantly slower than std::vector here, but it's still fast enough (237641788).

→ Reply