2D Fenwick-tree with combinatorics and modular arithmetic

Question

This is a contest problem;

Description:

In the winter, children started to build snowmen. The snowmen were becoming adorable, except for a detail: none of them had a nose. The king, touched, decided to give some of his carrots away so they could be distributed in rectangular-shaped regions of the Town. But the children of the city are greedy and do not mind putting several noses on their snowmen, no matter if other children end up with no noses to put on their snowmen.

Input:

The input describes, in sequence, all events that happened during the winter and consists of at most 10^5 lines. The first line of the input consists of two integers: N and M (\$1 ≤ N\$, \$M ≤ 10^3\$), which represent the dimensions of the Town. Each one of the following lines describes an event, characterised by the number of integers present in the line:

• If the line consists of three integers, X, Y and B (\$1 ≤ X ≤ N, 1 ≤ Y ≤ M\$, \$1 ≤ B ≤ 100\$), it means that a child has built B snowmen at the position in the Town of coordinates (X, Y);
• If the line consists of two integers, X and Y (\$1 ≤ X ≤ N, 1 ≤ Y ≤ M\$), it means that a child has destroyed all snowmen at the position of coordinates (X, Y);
• If the line consists of five integers, X1, Y1, X2, Y2 and C (\$1 ≤ X1 ≤ X2 ≤ N\$, \$1 ≤ Y1 ≤ Y2 ≤ M\$, \$1 ≤ C ≤ 10^3\$), it means that the king has awarded C identical carrots to be distributed among the snowmen built inside the rectangular-shaped region defined by the positions of coordinates (X1, Y1) and (X2, Y2), marking the end of a day.
• The last line of the input is always a five integer line.

Ouput:

For each day of the winter, ended in the input by a five integer line, print a line containing the number of the day and the number of possibilities for the distribution of the carrots among the snowmen at the delimited area. Consider that the counting of the days starts in 1. As the number of possibilities can be very large, print only the remainder that this value leaves when divided by 10^9 + 7. The input and output sample clarify further details about the output format.

---

#include <stdio.h> // *I/O*
#include <algorithm> // *swap*
#include <map>
#include <string.h>
#include <stdlib.h>

#define MOD 1000000007
#define MAX 1030

using namespace std;

typedef long long lld;

struct Fenwick2D {
    lld T[MAX][MAX];
    lld n, m;

    inline void clear(lld n, lld m) {
        for(lld i=1; i<=n; ++i)
            for(lld j=1; j<=m;++j)
                T[i][j] = 0;
        this->n = n;
        this->m = m;
    }

    inline void adjust(lld x, lld y, lld v) {
        for (lld i=x; i <= n; i += (i&-i))
            for(lld j=y; j <= m; j += (j&-j))
                T[i][j] += v;
    }

    inline lld rsq(lld x, lld y) {
        lld sum = 0;
        for(lld i=x; i; i -= (i&-i))
            for(lld j=y; j; j -= (j&-j))
                sum += T[i][j];
        return sum;
    }

    inline lld rsq(lld x1, lld y1, lld x2, lld y2){
        if(x1>x2)
            swap(x1,x2);
        if(y1>y2)
            swap(y1,y2);
        return  rsq(x2, y2) - rsq(x2, y1-1) - rsq(x1-1, y2) + rsq(x1-1, y1-1);
    }
};


lld expMod(lld a, lld b) {
    if (b == 0)
        return 1;
    if (b & 1)
        return a * expMod(a, b - 1) % MOD;
    long long y = expMod(a, b >> 1);
    return y * y % MOD;
}

map<lld,lld> memofat; //for memoized factorials
lld fat(lld n){
    if(memofat[n])
        return memofat[n];
    return memofat[n] = n*fat(n-1)%MOD;
}

//modular inverse with Fermat's Little Theorem
inline lld choose(lld n, lld k) {
    return fat(n) * expMod(fat(k) * fat(n - k) % MOD, MOD - 2) % MOD;
}


int readLine(char *arr){
    char ch;
    int size = 0;
    ch = getchar_unlocked();
    while(ch != '\n' && ch != EOF)
        *arr = ch,++arr,++size,ch = getchar_unlocked();
    *arr = 0;
    return size;
}

Fenwick2D T;
int main(void){
    memofat[0] = 1;
    char arr[1000];
    lld n,m,x1,y1,x2,y2,c,day = 0;

    readLine(arr);
    sscanf(arr,"%lld %lld",&n,&m);

    T.clear(n, m);

    int aux;
    while (readLine(arr)) {
        aux = sscanf(arr,"%lld %lld %lld %lld %lld",&x1,&y1,&x2,&y2,&c);

        //printf("%d\n",aux);
        if(aux == 2){
            T.adjust(x1, y1, -T.rsq(x1, y1,x1,y1));
        }

        else if(aux == 3){
            T.adjust(x1, y1, x2);
        }

        else if(aux == 5){
            lld qt_snow_man = T.rsq(x1, y1, x2, y2);
            printf("Day #%lld: %lld\n",++day,choose(qt_snow_man + c - 1,c));
        }
    }
}

Answer 1

Stack Usage?

I looked over your code and couldn't find any problems with it. So I ran it on my machine to see if it would work. But when I ran it, it got a segfault. When I debugged the program, it turned out that it wasn't a problem with the program logic, the problem was that the variable T was causing the stack to overflow.

T is defined as a local variable to main, so it is put on the stack. But the size of T is roughly 4 MB because of the big array inside of it. Apparently, my default stack limit isn't set up to handle that, and perhaps the judges setup is similar to mine? An easy fix for this is to make T be a global variable.