Can you explain why?

Simple answer: slow RAM, fast CPU and CPU caches. The problem is, that current CPUs are much faster than RAM - see this article for more information about the CPU-RAM gap. As a result, a CPU access to RAM costs a lot of CPU cycles. To reduce this problem, current CPUs have several levels of caches, which usually work best, when accessing memory addresses, that are close to each other.

You can try a simple example. Try running this program and measure its execution time:

#define N 10000

int a[N][N];

int main(void) {
    for (int i=0;i<N;i++) {
        for (int j=0;j<N;j++) {
            a[i][j] = 0;
        }
    }
}

Then switch indices used to access the array - change a[i][j] = 0 to a[j][i] = 0 - and measure the time again. Depending on your machine and compiler optimizations, the second version will be slower (on my machine it is about 5 times slower). You can try the same with different values of N.

In the first version, you access the array (or matrix) row-by-row. As each row is stored as a continuous memory block, you start with the lowest memory address and continue up to the highest memory address assigned to the array. This type of access is cache-friendly. On the other hand, in the second version you access the array column by column, which means skipping to a distant memory address in each iteration.

As for the original question, one of the problems could also be the log2 function, which seems to be quite slow. Try to replace it with a lookup table. See my solution for more details.

I used the observation that for a particular X suppose the initial Y mapping was Y0 , Then after each subsequent cycles X would be mapped to Y0 - 11 , Y0 - 2*11 and so on . So I could skip all the queries that mapped X to Y later than the leftmost position of maxima between X and Y0 using a simple formula .

What would be the complexity of your solution ?

I used this same observation, for each x find sum of [x,y] [x,y-11] and so on . The queries would be uniformly distributed among all x excluding those which are never visited. So, we can find no. of Y's for each x and calculate individual sum for all x's. However complexity-wise this would still be O(M) assuming we use sparse tables.But apparently, this is a better optimized version than going for all the M queries normally because for a chunk of queries, we are keeping x same,only changing Y. This makes significant difference in time of execution.