Here are some things that may help you improve your code.
Choose better variable names
I understand that N and Q are used within the problem description, but c and d are not and are very short and non-descriptive names.
Add comments
Comments do not add to compile time and help you (and others!) keep track of what is happening in the code.
Add error checking
One of the things I dislike about many of the programming contests is that they assume perfect input. In the real world, external data is not always formatted perfectly, so we would expect to do things like compensate for non-digit input or unexpected end of input. The obvious way to do this is to check the return value of scanf to make sure it actually read the values intended.
Rethink the algorithm
When we or numbers together the result is odd if any of the numbers was odd. Further, we can tell that a number is odd just by looking at the low bit of the number. In this problem, the result of a query can only be 1 (indicating that the result is even) if all of the values in the span are even. This suggests a much more elegant algorithm. Instead of storing all of the input numbers, just note the beginning and ending of each span of even numbers. Then for the queries, see if the values L and R lie completely within a single span. Here's one way to do that:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int main()
{
// N is number of input numbers
// Q is number of input queries
long N, Q;
if (scanf("%ld %ld\n", &N, &Q) != 2) {
return EXIT_FAILURE;
}
typedef struct {
long begin;
long end;
} span;
span even_spans[(N+1)/2];
long span_count = 0;
long i;
bool in_span = false;
/*
* Read each number from the input,
* and only examine the low bit.
*/
for (i = 0; N--; ++i) {
long m;
if (scanf("%ld", &m) != 1) {
return EXIT_FAILURE;
}
if (m & 1) {
if (in_span) {
even_spans[span_count++].end = i;
in_span = false;
}
} else { // it's even number
if (!in_span) {
even_spans[span_count].begin = i;
in_span = true;
}
}
}
if (in_span) {
even_spans[span_count++].end = i;
}
/*
* Process Q queries each of
* which is a pair of indices L, R
*/
while (Q--) {
long L, R;
if (scanf("%ld %ld", &L, &R) != 2) {
return EXIT_FAILURE;
}
// compensate for 1-based values
--L;
--R;
for (i = 0; i < span_count && L > even_spans[i].end; ++i) {
}
// only even if L and R are in the same even span
puts(i < span_count && L >= even_spans[i].begin
&& R < even_spans[i].end ? "1" : "0");
}
}
How it works
To explain in a bit more detail how this works, first let's consider a short input file.
test.in
11 5
1 2 4 6 5 8 10 11 12 14 16
1 5
1 4
2 3
2 4
2 5
Here's what the input looks like to this algorithm:
Input array:
| index |
number |
odd/even |
| 0 |
1 |
odd |
| 1 |
2 |
even |
| 2 |
4 |
even |
| 3 |
6 |
even |
| 4 |
5 |
odd |
| 5 |
8 |
even |
| 6 |
10 |
even |
| 7 |
11 |
odd |
| 8 |
12 |
even |
| 9 |
14 |
even |
| 10 |
16 |
even |
Here is the array of even spans that it creates:
| span number |
begin |
end |
| 0 |
1 |
4 |
| 1 |
5 |
7 |
| 2 |
8 |
11 |
Note that each span begins with the index of the first even number in a span, and ends one index after the final even number in a span.
Now for each of the query pairs \$L, R\$ mathematically the query is this
$$ \exists s \in S| ( L >= s_{\text{begin}}) \land (R < s_{\text{end}}) $$
Or in English, "there exists a span \$s\$ in the set of all spans \$S\$ such that \$L\$ is greater than or equal to \$s_{\text{begin}}\$ and \$R\$ is less than \$s_{\text{end}}\$. This code does a simple linear search; for huge data sets a binary search might be used.
Epilogue
Although the code above works, in that it produces correct answers, it takes much more time than the original version. If we combine @TobySpeight's excellent insight of storing a count of odd numbers instead of the original input array with the observation expressed here that a span will only result in an even number if the \$L,R\$ span lies completely within a span of even numbers, we can generate a much faster program at the expense of using more memory. Here's the code:
#include <stdio.h>
#include <stdlib.h>
int main()
{
unsigned long N, Q;
if (scanf("%lu %lu\n", &N, &Q) != 2)
return EXIT_FAILURE;
unsigned odd[N+1];
unsigned oddcount = 0;
unsigned *ptr = odd;
for (++ptr; N--; ++ptr) {
long m;
if (scanf("%ld", &m) != 1)
return EXIT_FAILURE;
m &= 1;
if (m) {
oddcount += 2;
}
*ptr = oddcount | m;
}
/*
* Process Q queries each of
* which is a pair L, R
*/
unsigned long L, R;
while (Q--) {
if (scanf("%lu %lu", &L, &R) != 2)
return EXIT_FAILURE;
puts(odd[L] != odd[R] || odd[L] & 1 ? "0" : "1");
}
}
How it works
As suggested by @TobySpeight, the array keeps track of the count of odd numbers. It allocates \$N+1\$ array items in the odd array and starts at odd[1] to eliminate the need for adjusting the 1-based query values. The addition is that within each array item we actually store two things: whether the particular input number was odd or even (bit 0) and the count of odd numbers so far (all the other bits of the unsigned value). Queries are handled by testing three conditions:
odd[L] != odd[R] true if there were any odd numbers betweenodd[L] & 1 true if the left limit was an odd numberodd[R] & 1 true if the right limit was an odd number
If any of these conditions are true, then the answer is 0 indicating an odd resulting value, otherwise the answer is 1 indicating an even resulting value. In reality, only the first two tests are needed, since the third test cannot be true if neither of the first two are.
Limitations
Although the program reads in unsigned long values for both \$N\$ and \$Q\$, the count of odd numbers is stored in an unsigned value. Further, we limit the range even more by using one bit of that number to indicate an odd or even value. Although the size of an unsigned is implementation-defined, the language of the standard yields the result that it must be at least 16 bits. Since we use one of those bits, the guaranteed maximum uniquely representable count is \$2^{15} - 1 = 32,767\$. After that, the value silently rolls over to zero. What that means for this program is that if the program's input ever has a span of odd numbers with a length that is an exact integral multiple of 32,768 (on systems with a 16-bit int) a query that picks a left location in the even span to the left of it, and a right location in the even span to the right of it, the program will falsely claim that the result is even. For systems with a 32-bit int, the value is 2,147,483,648.
If each input number is randomly selected, the probability that any given number is odd is \$P=\frac{1}{2} = 0.5\$. So the probability of randomly selecting 32,768 odd numbers in a row is \$3.052 \times 10^{-5}\$ or about 0.003%. The probability of selecting 2,147,483,648 odd numbers in a row is \$4.657 \times 10^{-10}\$ or about 0.000000047%. (For reference, according to this article, this is about ten times less likely than you winning the >US$700M Powerball lottery jackpot. I say "you" because I never buy lottery tickets; a practice which doesn't significantly alter my odds of winning!) However, we have no guarantee that the input values are selected randomly, and if I were running the contest, I would deliberately choose such inputs.
Interestingly, perhaps, it's on exactly this kind of input, with long spans of either even or odd numbers, that the first version I posted above works very well.
So the conclusion is that the program above is guaranteed to fail for certain ranges and types of values; whether that's acceptable is up to you.
