You are not logged in. Please login at www.codechef.com to post your questions!

×

[TLE] SPOJ Matsum Help

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

aryanc403's gravatar image

6★aryanc403
2.5k1516
accept rate: 10%

edited 21 Nov '18, 08:49


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:

include <stdio.h>

include <string.h>

define ms0(s) memset(s,0,sizeof s)

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;

}

link

answered 21 Nov '18, 09:53

sna902055's gravatar image

5★sna902055
425
accept rate: 7%

edited 21 Nov '18, 10:00

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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