ZOMCAV - Editorial

editorial
, , , ,
44 
 if l <= start and end <= r:
        SegTree[pos] += (end - start +1) * val
        if start != end:
            lazy[2*pos +1] += val
            lazy[2*pos + 2] += val
        return 
    
    mid = (start + end)//2
    range_update(SegTree, arr, lazy, start, mid, l, r, val, 2*pos+1)
    range_update(SegTree, arr, lazy, mid+1, end, l, r, val, 2*pos+2)
    SegTree[pos] = SegTree[2*pos+1] + SegTree[2*pos+2]
    return

Correct me if I got it wrong, but afaik lazy propagation states that once you store things in lazy array, you do not go on to update the children unless required by the query.

45 
void update(ll segTree[],ll lazy[],ll qlow,ll qhigh,ll low,ll high,ll val,ll pos)
{
   if(lazy[pos]!=0)
   {
       segTree[pos]+=(high-low+1)*lazy[pos];
       if(low!=high)
       {
           lazy[2*pos+1]+=lazy[pos];
           lazy[2*pos+2]+=lazy[pos];
       }
       lazy[pos]=0;
   }
   if(low>high or qlow>high or qhigh<low)
       return;
   if(qlow<=low and qhigh>=high)
   {
       segTree[pos]+=(high-low+1)*val;
       if(low!=high)
       {
           lazy[2*pos+1]+=val;
           lazy[2*pos+2]+=val;
       }
       return;
   }
   int mid=low+(high-low)/2;
   update(segTree,lazy,qlow,qhigh,low,mid,val,2*pos+1);
   update(segTree,lazy,qlow,qhigh,mid+1,high,val,2*pos+2);
   segTree[pos]=segTree[2*pos+1]+segTree[2*pos+2];
}

@vijju123
i check @kamesh_11 soltion it same as mine

46

It only cover partially range

47

CodeChef: Practical coding for everyone can anyone help me this?

48

Here’s a small testcase for which it fails, to help you debug:

1
5
4 2 2 3 1 
4 5 4 4 4

but more than that, your solution appears to be O(N^2), and so too slow to pass the larger testcases - you’ll get a TLE.

1 Like
49

it should show “NO” for that test case right?

50

No, it should be YES - what are the radiation levels for that testcase?

51

5 5 5 5 4 is this right?

52

I get:

4 4 4 5 4

After processing the first cave (radiation power: 4)

1 1 1 1 1

After processing the second cave (radiation power: 2)

2 2 2 2 1

After processing the third cave (radiation power: 2)

3 3 3 3 2

After processing the fourth cave (radiation power: 3)

4 4 4 4 3

After processing the fifth cave (radiation power: 1)

4 4 4 5 4
1 Like
53

yeah,for the fifth cave I took Ci - i instead of i - Ci.
thanks