×

[TLE] SPOJ Matsum Help

 1 Question My Soln My Approach - I used 2D segment Tree for point Updates and range Sum queries. Instead of the 2d array, I used maps for storing values. #Why does spoj have strict TL?? asked 21 Nov '18, 08:47 2.5k●1●5●16 accept rate: 10%

please use 2D binary index tree instead of 2D segment tree. spoj have strict time limit. here is solution using 2D binary index tree..
I hope it will help...

solution:

define SZ 1030

int bit[SZ][SZ]; int data[SZ][SZ]; int R, C;

void update(int r, int c, int val) {

int i,j;

for (i = r; i <= R; i += i & -i)

for (j = c; j <= C; j += j & -j)

bit[i][j] += val;


}

int sum(int r, int c) {

int i,j,s = 0;

for (i = r; i > 0; i &= i - 1)

for (j = c; j > 0; j &= j - 1)

s += bit[i][j];

return s;


}

int main() {

int t,cs=1;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
R = C = n;

ms0(bit); ms0(data);

char s[30];

while(scanf("%s",&s))
{
if(!strcmp(s,"SET"))
{
int r,c,val;

scanf("%d %d %d",&r,&c,&val);
r++,c++;
update(r, c, -data[r][c] + val);
data[r][c] = val;
}
else if(!strcmp(s,"SUM"))
{
int r1,c1,r2,c2;

scanf("%d %d %d %d",&r1,&c1,&r2,&c2);

r1++,c1++,r2++,c2++;

int res =0;

res+=sum(r2, c2) ;
res-=sum(r1 - 1, c2);
res-=sum(r2, c1 - 1);
res+=sum(r1 - 1, c1 - 1);

printf("%d\n",res);
}
else  break;
}
printf("\n");
}
return 0;


}

425
accept rate: 7%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,755
×1,136
×7

question asked: 21 Nov '18, 08:47

question was seen: 100 times

last updated: 21 Nov '18, 10:00