acash's blog

Need help in segment tree problem
By acash, history, 6 years ago, In English

I tried many test cases ,I am passing all of them But it is failing at test case 5 on codeforces. Since test case are quite large ,I am unable to figure out my error.Please forgive me if my question is not good. 55748387(My submission)

https://codeforces.net/contest/52/problem/C

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

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

Change removelazy(node1, l, r) to removelazy(node1, start, end1)

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

    Still getting wrong ,should i check also if the node is lazy or not while answering the query? Because i am not checking

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

      You need to use removelazy in your query function

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I added the removelazy in query part

I think there are many other issues in the implementation. I suggest you to check your implementation once again.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/52/submission/54744859 take a look at my submission

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

    Please can you tell me where I am doing the mistake?

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

      First of all you are consider 0 base indexing in your build() function so your left child is (node1 << 1) + 1 and right child is (node1 << 1) + 2 and your query() function is

      node query(int node1, int l, int r, int start, int end1) {

      if (tree[node1].lazy) {
    removelazy(node1, l, r);
}

node req;
if (l > end1 || r < start)return req;
if (l <= start && end1 <= r)return tree[node1];
int mid = (start + end1) >> 1;
node a = query((node1 << 1), l, r, start, mid);
node b = query((node1 << 1) + 1, l, r, mid + 1, end1);
merge1(req, a, b);
return req;

      }

      You do not consider if(tree[node1].lazy != 0) case in your query function

      → Reply