Return to Question

This is a contest problem; The entire description is here .

My code is taking time limit exceeded, so it is to slow. Is it possible to optimize it?. The time limit for this problem is just 1 second.

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.

Input sample:

4 6 
2 3 10 
3 6 5 
2 3 5 
1 1 2 
2 3 
3 2 1 
1 1 3 5 2 
1 4 10 
1 3 4 6 1

Output sample:

Day #1: 6 
Day #2: 15

This is a contest problem;

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;
struct Fenwick2D {
 int T[MAX][MAX];
 int n, m;
 
 inline void clear(int n, int m) {
 for(int i=1; i<=n; ++i)
 for(int j=1; j<=m;++j)
 T[i][j] = 0;
 this->n = n;
 this->m = m;
 }
 
 inline void adjust(int x, int y, int v) {
 for (int i=x; i <= n; i += (i&-i))
 for(int j=y; j <= m; j += (j&-j))
 T[i][j] += v;
 }
 
 inline int rsq(int x, int y) {
 int sum = 0;
 for(int i=x; i; i -= (i&-i))
 for(int j=y; j; j -= (j&-j))
 sum += T[i][j];
 return sum;
 }
 
 inline int rsq(int x1, int y1, int x2, int 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);
 }
};
long long expMod(long long a, long long 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<long long, long long> memofat; //for memoized factorials
long long fat(long long n){
 if(memofat[n])
 return memofat[n];
 return memofat[n] = n*fat(n-1)%MOD;
}
//modular inverse with Fermat's Little Theorem
inline long long choose(long long n, long long 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];
 int n,m,x1,y1,x2,y2,c,day = 0;
 
 readLine(arr);
 sscanf(arr,"%d %d",&n,&m);
 
 T.clear(n, m);
 
 int aux;
 while (readLine(arr)) {
 aux = sscanf(arr,"%d %d %d %d %d",&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){
 int qt_snow_man = T.rsq(x1, y1, x2, y2);
 printf("Day #%d: %lld\n",++day,choose(qt_snow_man + c - 1,c));
 }
 }
}

#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));
 }
 }
}

#include <stdio.h> // *I/O*
#include <algorithm> // *swap*
#include <map>
#define MOD 1000000007
#define MAX 1030
//FAST I/O
inline int fastRead_int(int *);
inline void fast_printInt (int n);
using namespace std;
struct Fenwick2D {
 int T[MAX][MAX];
 int n, m;
 
 inline void clear(int n, int m) {
 for(int i=1; i<=n; ++i)
 for(int j=1; j<=m;++j)
 T[i][j] = 0;
 this->n = n;
 this->m = m;
 }
 
 inline void adjust(int x, int y, int v) {
 for (int i=x; i <= n; i += (i&-i))
 for(int j=y; j <= m; j += (j&-j))
 T[i][j] += v;
 }
 
 inline int rsq(int x, int y) {
 int sum = 0;
 for(int i=x; i; i -= (i&-i))
 for(int j=y; j; j -= (j&-j))
 sum += T[i][j];
 return sum;
 }
 
 inline int rsq(int x1, int y1, int x2, int 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);
 }
};
long long expMod(long long a, long long 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<long long, long long> memo; //for memoized factorials
long long fat(long long n){
 if(memo[n])
 return memo[n];
 return memo[n] = n*fat(n-1)%MOD;
}
//modular inverse with Fermat's Little Theorem
inline long long choose(long long n, long long k) {
 return fat(n) * expMod(fat(k) * fat(n - k) % MOD, MOD - 2) % MOD;
}
Fenwick2D T;
int main(void){
 memo[0] = 1;
  
 int n,m,x1,y1,x2,y2,c,day = 0;
 fastRead_int(&n);
 fastRead_int(&m);
 
  T.clear(n, m);
 while(1) {
  if(fastRead_int(&x1) == EOF)
 break;
 
 //just two elemnts on line
 if(fastRead_int(&y1) == -2){
 T.adjust(x1, y1, -T.rsq(x1, y1,x1,y1));
 continue;
 }

 if(fastRead_int(&x2) == -2){
 T.adjust(x1, y1, x2);
 continue;
 }
 
 fastRead_int(&y2),fastRead_int(&c);
 int qt_snow_man = T.rsq(x1, y1, x2, y2);
 
 printf("Day #%d: %lld\n",++day,choose(qt_snow_man + c - 1,c));
 }
}

#define gc getchar_unlocked()
inline int fastRead_int(int *x) {
  char c = gc;
 if(c == EOF)
 return EOF;
 *x = 0;
  //int neg = 0;
  for(; ((c<48 || c>57) && c != '-');
 c = gc);
 //if(c=='-')
 // neg = 1,c = getchar_unlocked();
 for(; c>47 && c<58 ; c = gc)
 *x = ((*x)<<1) + ((*x)<<3) + c - 48;
 //if(neg)
 // *x = -(*x);
 if(c == '\n')
 return -2;
  return 1;
}
#define pc(x) putchar_unlocked(x);
inline void fast_printInt (int n)
{
 if(n < 0){pc('-'); n = -n;}
 if (n == 0) { pc('0'); pc('\n'); return ;}
 int abc = n, rev, count = 0;
 rev = abc;
 while ((rev % 10) == 0){ count++; rev /= 10;} //obtain the count of the number of 0s
 rev = 0;
 while (abc != 0) { rev = (rev<<3) + (rev<<1) + abc % 10; abc /= 10;} //store reverse of N in rev
 while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;}
 while (count--) pc('0');
 pc('\n');
}

#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;
struct Fenwick2D {
 int T[MAX][MAX];
 int n, m;
 
 inline void clear(int n, int m) {
 for(int i=1; i<=n; ++i)
 for(int j=1; j<=m;++j)
 T[i][j] = 0;
 this->n = n;
 this->m = m;
 }
 
 inline void adjust(int x, int y, int v) {
 for (int i=x; i <= n; i += (i&-i))
 for(int j=y; j <= m; j += (j&-j))
 T[i][j] += v;
 }
 
 inline int rsq(int x, int y) {
 int sum = 0;
 for(int i=x; i; i -= (i&-i))
 for(int j=y; j; j -= (j&-j))
 sum += T[i][j];
 return sum;
 }
 
 inline int rsq(int x1, int y1, int x2, int 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);
 }
};
long long expMod(long long a, long long 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<long long, long long> memofat; //for memoized factorials
long long fat(long long n){
 if(memofat[n])
 return memofat[n];
 return memofat[n] = n*fat(n-1)%MOD;
}
//modular inverse with Fermat's Little Theorem
inline long long choose(long long n, long long 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];
 int n,m,x1,y1,x2,y2,c,day = 0;
 
 readLine(arr);
 sscanf(arr,"%d %d",&n,&m);
 
 T.clear(n, m);
 
 int aux;
 while (readLine(arr)) {
 aux = sscanf(arr,"%d %d %d %d %d",&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){
 int qt_snow_man = T.rsq(x1, y1, x2, y2);
 printf("Day #%d: %lld\n",++day,choose(qt_snow_man + c - 1,c)); }
 }
}