flipping coins(medium)

Time limit is -2sec in this question… wt is this i cnt undrstnd… I think my dis below code is smallest of all…still it showing time liimit exceeded… :frowning:

#include<stdio.h>
main()
{
	int arr[1000000];
	int m,a,b,i,count[1000000],n,q,j;
	scanf("%d",&n);
	scanf("%d",&q);
	while(q)
	{
		scanf("%d %d %d", &m, &a, &b);
		if(m==0)
		{
			for(i=a;i<=b;i++)
			{
				if(arr[i]==0)
				{
					arr[i]=1;
					count[i]=1;
				}
				else if(arr[i]==1)
				{
					arr[i]=0;
					count[i]=0;
				}
				else
				{
					arr[i]=1;
					count[i]=1;
				}
			}
		}
		if(m==1)
		{
		  j=0;
			for(i=a;i<=b;i++)
			{
				if(count[i]==1)
				{
					j++;
				}
			}
			printf("%d",j);
			printf("\n");
		}
		q--;
	}
	return 0;
}

The length of code has no correlation to the time it takes to execute. You are using a sub optimal algorithm for the problem. Simply scanning the elements from left to right will not work since there are lot of elements and lots of queries. You need to find a way out to do it fast enough.

3 Likes

use segment trees

1 Like