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

×

Can anybody please explain me this code of question SEACO(september long challenge).

asked 20 Sep '17, 16:06

deepak_097's gravatar image

4★deepak_097
933
accept rate: 0%


count = (count + B[i+1])%MOD;

Seems to me number of times common X will be executed, ONLY considering the commands executed from end till now. (i.e. not including command X in list right now)

B[i+1] = (count + 1)%MOD;

Including X in list, hence increasing count by 1.

if(t[i] == 1)
      {
        A[l[i] - 1] = (A[l[i] - 1] + B[i+1])%MOD;
        A[r[i]] = (A[r[i]] + MOD - B[i+1])%MOD;
        //printf("A[%d]=%d A[%d]=%d\n",l[i]-1,A[l[i]-1],r[i],A[r[i]]);
      }

Standard difference Array. Say your array is {5,10,11,2}. Then difference array arr[i+1]-arr[i] is {5,1,-9}. You know you know arr[1]=5. You can give arr[i] as-

arr[i]=arr[i-1]+diff[i-1];//Eg- arr[1]==arr[0]+diff[0]=5+5=10

B[l[i]-1] = (B[l[i]-1] + MOD - B[i+1])%MOD;
        B[r[i]]   = (B[r[i]] + B[i+1])%MOD;

Same technique for Type 2 commands as well.

And I think this was pretty much it of this code. In case your doubt persists, please check editorial, he has explained this approach there.

link

answered 20 Sep '17, 18:56

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

Here why two array is considered instead of one ? A[l[i] - 1] = (A[l[i] - 1] + B[i+1])%MOD; A[r[i]] = (A[r[i]] + MOD - B[i+1])%MOD;


B[l[i]-1] = (B[l[i]-1] + MOD - B[i+1])%MOD; B[r[i]] = (B[r[i]] + B[i+1])%MOD;

these 4 lines still i am unable to understand.

(20 Sep '17, 21:40) deepak_0974★

Array is is to store Type 1 queries, Array B is to store results of Type 2 queries, which in turn affect Type 1 queries (and are hence counted when Type==1).

(20 Sep '17, 22:36) vijju123 ♦♦5★
Answer is hidden as author is suspended. Click here to view.

answered 20 Sep '17, 19:06

raj79's gravatar image

2★raj79
(suspended)
accept rate: 10%

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:

×427
×59
×8

question asked: 20 Sep '17, 16:06

question was seen: 464 times

last updated: 20 Sep '17, 22:36