ajit's blog

Weird issue with my solution for problem H of Codeforces Round 966
By ajit, history, 3 months ago, In English

Hi,

While solving problem H of the recent Codeforces Div3 round (link), I came across the following issue (after hours of debugging):

In my solution, I had to clear up the segment tree after every test case, so I kept track of all the elements I interacted with in an STL container. The issue is that if I use std::set for keeping track of changed elements in the segment tree, I have no issues, but if I use std::vector, I get a weird runtime error on test 4. Here are my two solutions:

  • Accepted solution (using std::set variable called changed_elements in segtree structure) link
  • Runtime error solution (using std::vector variable called changed_elements in segtree structure) link

Can anyone tell me what's causing this runtime error?

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

»
3 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

You are iterating over the changed_elements vector and calling set function which pushes into this vector. push_back for vector invalidates iterators, so it's no wonder you are getting a runtime error. std::set insert doesn't invalidate iterators, so that's why there is no runtime error.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oops, I got your point. Thanks !

    → Reply