facug91's blog

Range Sum Query Static
By facug91, 10 years ago, In English

Hi everyone, I'm looking for problems involving RSQ static. I know it's a very simple technic, but I need it for a class, to give them some problems to practice. I've solved a lot of problems with it, but I've never classified them, and weirdly I can't find any of them googling. Until now I have this two: http://mirror.codeforces.com/problemset/problem/313/B http://coj.uci.cu/24h/problem.xhtml?abb=2111 If someone has some others, from any judge, I'll appreciate it. Thanks!

Tags dp, rsq
  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Try the last problem from here: https://cemc.math.uwaterloo.ca/contests/computing/2009/stage1/seniorEn.pdf.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Thank you so much zxqfl, I didn't know that problem, and it's very interesting :). Anyway, I've been trying to solve it for a few hours, and always receive TLE. I've made the calculus, and should pass (tight, but still pass). Surely my approach isn't the correct one, and I'm thinking something wrongly. Here's my code. Basically what I did is update the first element a circle touches in each row, and the next element of the last one that a circle touch (range update, like in Fenwick Tree), then traverse all the grid updating each cell and saving the maximums. It should be O(n*m*3), around 9x10⁷ operations... I don't know, could you give me some clue about the solution? haha And thanks in advance :)

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Your solution is correct. The grader you're using to check your solution probably requires constant optimizations as well, so I tried to do some here (read the comments).

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

      So I wasn't as wrong as I thought haha. Thank you ffao, with your help I've finally got AC :)

      → Reply