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

×

MULTQ3 - Editorial

4
2

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

The problem can be solved using segment trees. Every node of the tree stores the following data :

1) tree0[k] : In the range [low..high] covered by this node, how many numbers are divisible by 3 considering just additions performed on numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2
2) tree1[k] : In the range [low..high] covered by this node, how many numbers leave a remainder of 1 when divided by 3 considering just additions performed on numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2
3) add[k] : What is the quantity which is added to all numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2

This question is marked "community wiki".

asked 29 Nov '12, 12:15

admin's gravatar image

0★admin ♦♦
17.4k347487515
accept rate: 36%


Can we solve it using BIT? If yes then How??

link

answered 14 Mar '13, 19:28

master_pk's gravatar image

2★master_pk
152247
accept rate: 0%

plz elaborate your explaination....its too difficult too understand from such 3 confusing statements u have mentioned just for the sake of editorial.. - _ -

link

answered 31 May '16, 01:21

kunnu96's gravatar image

4★kunnu96
913
accept rate: 0%

Can anyone help me, pls ?? I use Segment Tree but I got Wrong Answer and I don't know why. This is my submission, help me, please. https://www.codechef.com/viewsolution/13414560

link

answered 01 May, 08:41

tieunhi's gravatar image

3★tieunhi
1
accept rate: 0%

Hey..I have solved this question using seg-trees but Im getting WRONG ANSWER. Here is my code. https://www.codechef.com/viewsolution/15771326

Thanks in advance.

link

answered 11 Oct, 19:39

devpahuja's gravatar image

3★devpahuja
11
accept rate: 0%

-1

include<cstdio>

using namespace std;

int main() { int n,q; scanf("%d %d", &n, &q);

    int a[3],coin[100001]={0},head;

   while(q--)
    {
        for(int j=0;j<3;j++)
            scanf("%d", &a[j]);
            head=0;

        if(a[0] == 0)
        {
               for(int i=a[1];i<=a[2];i++)
                    coin[i]++;
        }
        else
        {
             for(int i=a[1];i<=a[2];i++)
                if(coin[i]%3 == 0)
                    head++;

             printf("%d\n" , head);
        }
    }

}

WHY is this giving TLE error???

link

answered 19 Oct '14, 14:56

piyushjain1555's gravatar image

1★piyushjain1555
-51
accept rate: 0%

-2

include<cstdio>

using namespace std;

int main() { int n,q; scanf("%d %d", &n, &q);

    int a[3],coin[100001]={0},head;

   while(q--)
    {
        for(int j=0;j<3;j++)
            scanf("%d", &a[j]);
            head=0;

        if(a[0] == 0)
        {
               for(int i=a[1];i<=a[2];i++)
                    coin[i]++;
        }
        else
        {
             for(int i=a[1];i<=a[2];i++)
                if(coin[i]%3 == 0)
                    head++;

             printf("%d\n" , head);
        }
    }

}

WHY is this giving TLE error???

link

answered 19 Oct '14, 14:55

piyushjain1555's gravatar image

1★piyushjain1555
-51
accept rate: 0%

:) You must use data structure in order to process any query in O(logn), not O(n), which let your solution TLE :)

(05 Nov '14, 13:22) leduongtuananh2★
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:

×12,283
×1,934
×7
×5

question asked: 29 Nov '12, 12:15

question was seen: 7,886 times

last updated: 11 Oct, 19:39