Блог пользователя acash

Автор acash, история, 5 лет назад, По-английски

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://mirror.codeforces.com/contest/52/problem/C

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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