runtime error in rectangular queries

general
,
1

#include<stdio.h>
//#include<conio.h>
int main()
{
//clrscr();
int a[300][300],test[1000],count[10],m,n,c,re,i,j,p,q,r,s,l;
long qu;
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
scanf("%ld",&qu);
}
for(re=0;re<qu;re++)
{
c=0;
for(i=0;i<10;i++)
count[i]=0;
scanf("%d %d %d %d",&p,&q,&r,&s);
for(i=p-1;i<r;i++)
{
for(j=q-1;j<s;j++)
{
m=a[i][j];
–m;
count[m]++;
}
}
for(i=0;i<10;i++)
if(count[i]!=0)
c++;
test[re]=c;
}
for(i=0;i<qu;i++)
printf("%d\n",test[i]);
// getch();
return 0;
}
not able to get the runtime error in this code!please help!

2

The number of queries in the question can be at max 105…but your array test[] is of size 103…hence this might be the reason behind runtime error…

1 Like
3

Although runtime error is rectified…but you code needs some optimization to pass the test cases in time…I have tried to submit the rectified code and it gives TLE…You can go for some precomputation before entertaining the queries

4

you are right after rectifying the runtime error still it gives tle

5

can u suggest some precomputation thats needed?

6

You can pre-compute the cumulative frequencies of each number row-wise…then at the time of entertaining queries…run a loop just to iterate the rows and check for the occurrences of each number by subtracting cumulative frequencies(i.e. arr[i][y2][k]-arr[i][y1][k])…where k is the number whose cumulative frequency you want to check till arr[i][j].

7

what do cumulative frequency mean?

8

^ @anonymousins Check this to know about cumulative frequency.

9

what do c.f mean

10

No need to get confused with cumulative frequency…what I mean to say is you need to keep track of how many times a number has occurred before…

11

You can refer to my solution for better understanding of how to precompute…
http://www.codechef.com/viewsolution/3037809

12

Is this what u are saying?
for each row maintain an array for cumulative frequencies…
i didn’t get “run a loop just to iterate the rows and check for the occurrences of each number by subtracting cumulative frequencies”
i am uncomfortable with 3d arrays

13

I have 2 doubts which i am totally unable to get.
1.Suppose you have a matrix and count array for every row

1 2 3      1 1 1 0 0 0 0 0 0 0
4 5 6      0 0 0 1 1 1 0 0 0 0
7 8 9      0 0 0 0 0 0 1 1 1 0

now suppose you enter a query 2 2 3 3.Now from count array how can we get the answer.Suppose we travel the count array from row 2 you have recorded an occurence of 4 there but it is not in your query part.
so what to do?

2.are we going to travel all elements included in the query?