×

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".

19.3k348495534
accept rate: 36%

 6 Can we solve it using BIT? If yes then How?? answered 14 Mar '13, 19:28 152●2●4●7 accept rate: 0%
 0 plz elaborate your explaination....its too difficult too understand from such 3 confusing statements u have mentioned just for the sake of editorial.. - _ - answered 31 May '16, 01:21 4★kunnu96 102●4 accept rate: 0%
 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 answered 01 May '17, 08:41 4★tieunhi 1 accept rate: 0%
 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. answered 11 Oct '17, 19:39 1●1 accept rate: 0%
 0 How can one identify that this should be solved through segment tree ? are there any ways to identify such problems (related to segment etc) ? also is there any other way to solve this ? answered 30 Jan, 17:59 1●1 accept rate: 0%
 0 @piyusjain1555 its a question of "lazy propagation" in "segment tree"... looks like you were a beginner for coding... so you can google and learn how to do this type of questions... u have have a look at FLIPCOIN which is similar to this question.. answered 05 Apr, 22:12 1.1k●1●8 accept rate: 27%
 0 The following is the idea. Initially, all the numbers are divisible by 3. tree[node][0] = hi - lo + 1 Now, let's say we are updating range [lo .. hi] and hi - lo + 1 = 4. Each update to range [lo .. hi] of tree node moves the count in the following fashion. Update number 1 -> all 0's will be 1. 0000 -> 1111 and we save these numbers in tree[node][1] Update 1: tree[node][1] = tree[node][0]. Update number 2 -> all 1's will be 2. 1111 -> 2222. So we save these numbers in tree[node][2] Update 2: tree[node][2] = tree[node][1]. Update number 3 -> all 2's will be 3. 2222 -> 3333. They are now divisible by 3, so we save these numbers in tree[node][0] Update 3: tree[node][0] = tree[node][2] and so on. answered 19 Apr, 07:22 0★c137 1 accept rate: 0%

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

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)

}
}


}

WHY is this giving TLE error???

-51
accept rate: 0%

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

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)

}
}


}

WHY is this giving TLE error???

-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)
 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:

×15,005
×2,474
×7
×6

question asked: 29 Nov '12, 12:15

question was seen: 9,072 times

last updated: 20 Apr, 23:08