### zoooma13's blog

By zoooma13, history, 4 months ago, ,

IOI tasks are now available on IOI Website.

Live Scoreboard

•
• +62
•

 » 4 months ago, # |   +8 Can someone elaborate how to solve the third subtask in seats problem.3. (20 points) H <= 1000, W <= 1000, Q <= 5000Thanks in advance.
•  » » 4 months ago, # ^ |   +17 SpoilerMy approach: Let Bk be the bounding box of all numbers from 1 to k. If area(Bk) = k, then Bk is beautiful. Conversely, if R is a beautiful rectangle and area(R) = k, then area(Bk) = k. And finally, if area(Bk) = k, then area(Bk + 1) > k, because if R = Bk is beautiful, then either Rk + 1 or Ck + 1 is outside of the bounding box Bk. Without loss of generality let it be Rk + 1. It follows that k + 1 is the first contestant at row Rk + 1. So, all we need to remember is the contestant with the lowest id that is in the row i, and the contestant with the lowest id that is in the column j. We can do this by simply maintaining an ordered set of the indices of contestants for each row and column. This can be maintained in per query. Using this, we obtain H + W candidates on the beautiful rectangles in O(H + W) time and we simply check all of them.To check a candidate for a rectangle, we have a segment tree for calculating the minimum/maximum row/column on a range. This gives us time algorithm to process one query.Combined together, this is .
•  » » » 4 months ago, # ^ |   +8 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, # ^ |   0 Can you explain more on how it can be improved?
•  » » » 4 months ago, # ^ |   0 Would 10^7 segtree operations really pass?
•  » » 4 months ago, # ^ | ← Rev. 4 →   +3 My solution involves just iterating all the positions and recomputing for each query. You will get a total of 37 points with this. SolutionLets define a beautiful box Bk as a box containing only numbers 0 to k-1 I would sore in array arr[id] = {r, c} the position of each contestant. Then for a bounding box Bk to exist the prefix arr[0..k] should form a rectangle. For that I get the min/max for column/row in the prefix of size k and check if the rectangle is exactly of area k. If yes then that is one box. So I compute this in O(HW) and build an array stating if Bk is a bounding box or not. When each query arrives I will update positions a and b and recompute the positions of the array in the range a and b in O(|a - b|).
 » 5 weeks ago, # |   -9 Someone help me problem werewolf :D . I don't have any idea about this problem
•  » » 5 weeks ago, # ^ |   +12 Read the editorial at the official IOI website.LooOoOoOOOooOoLooOooOooOooL. LMAO. ROFL.Are you even too lazy to google that?
•  » » » 5 weeks ago, # ^ |   0 nopeeeee. i attemp many times but i don't find :D