acash's blog

By acash, history, 5 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

| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    5 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

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

      You need to use removelazy in your query function

»
5 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.

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

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

    • »
      »
      »
      5 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