one0one's blog

By one0one, history, 6 years ago, In English

Hello, I tried segment tree with lazy propagation on this problem. Implementation is taken from this article. I got TLE on test#7.

In my opinion, my solution is nlog(n). updateRange works in log(n) time and I call it q times hence qlog(n). Then I call n times queryRange, it's runtime also log(n) hence nlog(n). Overall complexity is nlog(n) + qlog(n). It should work well in given constraints but unfortunately I got TLE.

So what I am missing?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your problem is that

void build(vector<long long> a, int node, int start, int end)

makes a copy of the vector over and over. To not make a copy use

void build(vector<long long> &a, int node, int start, int end)