July Cook Off question ANDMIN segment trees, lazy propagation, not gettting AC

#include<stdio.h>
#include
#include<math.h>
#include<string.h>
using namespace std;

struct SegmentTreeNode {

	int start, end;
	int mini;
	bool bits[32];//false = 0, true = 1


	void assignLeaf(int value ) {
        int tmp = value;
        for ( int i = 0; i < 32; i++ ) {
            if ( ( tmp & 1 ) == 0 )  {
                bits[i] = false;
            }
            else {
                bits[i] = true;
            }
            tmp >>=1;
        }
        mini = value;
	}

	void merge(SegmentTreeNode& left, SegmentTreeNode& right) {

		mini = min( left.mini, right.mini );

		for ( int i = 0; i < 32; i++ ) {
            if ( left.bits[i] == true || right.bits[i]== true ) {
                bits[i] = true;
            }
            else {
                bits[i] = false;
            }
		}
	}

	int query() {
		return mini;
	}


    bool isUpdateRequired(int updateValue ) {

        bool updateBits[32];
        for ( int i = 0; i < 32; i++ ) {
            if ( ( updateValue & 1 )== 0 ) {
                updateBits[i] = false;
            }
            else {
                updateBits[i] = true;
            }
        }

        for ( int i = 0; i < 32; i++ ) {
            if ( updateBits[i] == false && bits[i] == true ) {
                return true;
            }
        }
        return false;
    }
};


template<class InputType, class UpdateType, class OutputType>
class SegmentTree{
	SegmentTreeNode* nodes;
	int N;

public:
	SegmentTree(InputType arr[], int N ) {
		this->N = N;
		nodes = new SegmentTreeNode[getSegmentTreeSize(N)];
		buildTree(arr,1, 0, N-1);
	}
	~SegmentTree() {
		delete[] nodes;
	}

	void update(int startRange, int endRange, UpdateType updateValue ) {
		update(1, startRange, endRange, updateValue);
	}

	OutputType query(int startRange, int endRange ) {
		SegmentTreeNode result = query(1,startRange, endRange);
		return result.query();
	}
private:

	SegmentTreeNode query(int stIndex, int startRange , int endRange ) {
		SegmentTreeNode result;

		if ( nodes[stIndex].start == startRange && nodes[stIndex].end == endRange ) {
			result = nodes[stIndex];

			return result;
		}

		int mid = ( nodes[stIndex].start + nodes[stIndex].end ) / 2;
		int leftIndex = 2 * stIndex;
		int rightIndex = leftIndex + 1;

		if ( startRange > mid ) {
			result = query(rightIndex, startRange, endRange);
		}
		else if ( endRange <= mid ) {
			result = query(leftIndex, startRange, endRange);
		}
		else {
			SegmentTreeNode leftNode = query(leftIndex, startRange, mid);
			SegmentTreeNode rightNode = query(rightIndex, mid + 1, endRange);
			result.merge(leftNode,rightNode);
			result.start = leftNode.start;
			result.end = rightNode.end;
		}

		return result;
	}

	void update(int stIndex, int startRange, int endRange, UpdateType updateValue ) {

        //if leaf node
        if ( nodes[stIndex].start == nodes[stIndex].end ) {
            nodes[stIndex].mini = (nodes[stIndex].mini & updateValue);
            int tmp = nodes[stIndex].mini;
            for ( int i = 0; i < 32; i++ ) {
                if ( ( tmp & 1 ) == 0 )  {
                    nodes[stIndex].bits[i] = false;
                }
                else {
                    nodes[stIndex].bits[i] = true;
                }
                tmp >>=1;
            }
			return;
        }

        //if need for anding exists
		if ( nodes[stIndex].start == startRange && nodes[stIndex].end == endRange ) {
			if (nodes[stIndex].isUpdateRequired(updateValue) ) {

                int mid = ( nodes[stIndex].start + nodes[stIndex].end ) / 2;
                int leftIndex = 2 * stIndex;
                int rightIndex = leftIndex + 1;

                if ( startRange > mid ) {
                    update(rightIndex, startRange, endRange, updateValue);
                }
                else if ( endRange <= mid ) {
                    update(leftIndex, startRange, endRange, updateValue);
                }
                else {
                    update(leftIndex, startRange, mid , updateValue);
                    update(rightIndex, mid + 1, endRange, updateValue);
                }
                nodes[stIndex].merge(nodes[leftIndex], nodes[rightIndex]);
            }
		}


 	}

	void buildTree(InputType arr[], int stIndex, int first, int last ) {

		nodes[stIndex].start = first;
		nodes[stIndex].end = last;

		if ( first == last ) {
			nodes[stIndex].assignLeaf(arr[first]);
			return;
		}

		int mid = ( first + last ) / 2;
		int leftNodeIndex = 2 * stIndex;
		int rightNodeIndex = leftNodeIndex + 1;

		buildTree(arr,leftNodeIndex,first, mid);
		buildTree(arr,rightNodeIndex,mid+1, last);
		nodes[stIndex].merge(nodes[leftNodeIndex],nodes[rightNodeIndex]);
	}

	long long getSegmentTreeSize(int N ) {
		long long size = 1;
		for ( ; size< N; size<<=1) {
			;
		}
		return size<<1;
	}
};


int main() {

    int n, q, l, r, x, choice;
	int arr[100000];

	cin>>n>>q;

	for ( int i = 0; i < n; i++ ) {
		cin>>arr[i];
	}

	SegmentTree<int, int, int> st(arr, n);

	while ( q-- ) {
		cin>>choice;
		cin>>l>>r;
		if ( choice == 0 ) {
			//query 0 l r
			cout<<st.query(l-1,r-1)<<endl;
		}
		else {
			//1 l r x update
			cin>>x;
			st.update(l-1,r-1,x);
		}
	}
    return 0;
}

The above is the code.
Here is the link to the problem statement:

Can someone please tell me where the bug is?

Why doesn’t anyone want to reply?

144 views, 0 answers, eethara yaake?

swalpa bega heli, sharing is caring

are you getting a TLE?

Btw you have made it quite complex , actually theres no need to keep an array of 32 bits ! you can just keep an integer to store BitwiseOR over the range let this integer be called bit . And then your function isupdaterequired only needs to check :

if((bit&updatevalue)==bit)return false;

else return true;

quite a pain of debugging will be resolved

I am getting WA. It passes sample test cases. I used bool array to make things explicitly clear to myself about what I was doing. I felt I could end up making errors more easily if I am not careful during bit manipulation.

@gonecase though i am not sure , but still , i see something suspicious in your isUpdateRequired function . When you are filling bool updatebits[] , you should shift updateValue . Shouldnt it be

if ( ( ( updateValue>> i ) & 1 )== 0 ) {

updateBits[i] = false;

}

theres no bit shift going on in your code :slight_smile:

1 Like

Thanks a lot bro. There were 2 bugs. One was the one you pointed out. Another was that the update() function would not work if there was no match between start and end range of the update and the start and end range of the node in question. Finally got an AC. Thanks for helping out again :))

sharing is caring :slight_smile: