zoooma13's blog

By zoooma13, history, 4 months ago, In English,

IOI tasks are now available on IOI Website.

Tasks : combo seats werewolf

Live Scoreboard

 
 
 
 
  • Vote: I like it  
  • +62
  • Vote: I do not like it  

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone elaborate how to solve the third subtask in seats problem.

3. (20 points) H <= 1000, W <= 1000, Q <= 5000

Thanks in advance.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it
    Spoiler
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      To check a candidate for a rectangle, we have a segment tree for calculating the minimum/maximum row/column on a range. -> we can improve it to O(H+W) easily. (update r1, r2, c1, c2). Overall time complexity is O(HW + Q(H+W)).

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

      Would 10^7 segtree operations really pass?

  • »
    »
    4 months ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    My solution involves just iterating all the positions and recomputing for each query. You will get a total of 37 points with this.

    Solution
»
5 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Someone help me problem werewolf :D . I don't have any idea about this problem

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Read the editorial at the official IOI website.

    LooOoOoOOOooOoLooOooOooOooL. LMAO. ROFL.

    Are you even too lazy to google that?