MarioYC's blog

BIT solution for Codeforces #91 E
By MarioYC, 9 years ago, In English
I was looking at solution 810236 from hpfdf and also other users, who only for every query "add l r d" do a for loop from l to r and make at most two update operations in a BIT.

Why does this work? I think something like this would do more than 109 operations.
 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (10)
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think the data is rondom,so the length of each query range is not large.I also used a BIT to solve this problem although it is not the best solution.
→ Reply
»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

what exactly is almost lucky number? sorry if it is stupid but sb pls answer

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is a condition given in the problem statements of codeforces beta round 91. If you read any problem statement from this round I hope you will understand.

    → Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I think that because of this condition:

The operations are such that after all additions the array won't have numbers that would exceed 104

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please provide testcase 26 of A problem

→ Reply
»
4 months ago, # |
  Vote: I like it -10 Vote: I do not like it

I think if code give "YES" for 141(input) then it will also work fine for test case 26(799).

141/47=3

141 is not lucky 47 is lucky

141 gets evenly divided by 47

→ Reply