MINIAND ENIGMA Editorial

PROBLEM LINK:

MINIAND - Minion AND Range ENIGMA-Plinth’20
Author - tds115
Editorialist - Priyam Khandelwal

DIFFICULTY:

Easy

PREREQUISITES:

Prefix sums, Bitwise AND

PROBLEM:

Given an array, find whether Bitwise AND of a range A[L], A[L+1], ... A[R] is even or odd.

Explanation

The main observation here is that if there is atleast one even number in the required range, answer will be even (Think why?).
To solve the reduced problem of finding whether there is an even number in the range, make a prefix array which will tell number of even numbers upto index i. Then for each query calculate pre[R] - pre[L-1]. If the value is greater than 0 then the answer is “EVEN” else the answer is “ODD”.

Author solution

Author’s Solution

Why my algorithm exceeded time limit?

int main() {
	int T;
	cin>>T;
	while(T--)
	{
	    int N,Q;
	    
	    cin>>N;
	    int Ai[N] ={};
	    
	    int j =0;
	    for(int i=0;i<N;i++)
	    {
	        int tmp;
	        cin>>tmp;
	        if((tmp&1)==0)
	        {
	            
	            for(;j<I;)
	            {
	                Ai[j++]=I;
	            }
	            Ai[i]=-1;
	            j=I+1;
	        }
	    }
	    
	    cin>>Q;
	    for(int i=0;i<Q;i++)
	    {
	        int i_pos,L,R;
	        cin>>L>>R;
	        i_pos=Ai[L-1];
	        switch (i_pos)
	        {
	            case -1:
	                cout<<"EVEN"<<endl;
	                break;
	             case 0:
	                cout<<"ODD"<<endl;
	                break;
	             default:
	                if(R>=i_pos+1)
        	        {
        	            cout<<"EVEN"<<endl;
        	        }
        	        else
        	        {
        	            cout<<"ODD"<<endl;
        	        }
        	        break;
	        }
	        
	    }
	    
	}
	return 0;
}

I understand, that’s because I need to include the following two statements:
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);