# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3520 |

2 | tourist | 3461 |

3 | Um_nik | 3367 |

4 | apiadu | 3351 |

5 | mnbvmar | 3332 |

6 | Benq | 3330 |

7 | LHiC | 3276 |

8 | TLE | 3271 |

9 | Radewoosh | 3251 |

10 | ecnerwala | 3241 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 189 |

2 | Errichto | 188 |

3 | tourist | 180 |

4 | Radewoosh | 173 |

5 | vovuh | 166 |

6 | pikmike | 165 |

7 | ko_osaga | 162 |

8 | Um_nik | 160 |

9 | rng_58 | 155 |

10 | Petr | 152 |

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/27/2020 07:30:56 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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

Thanks in advance.

SpoilerMy approach: Let

B_{k}be the bounding box of all numbers from 1 tok.If

area(B_{k}) =k, thenB_{k}is beautiful. Conversely, ifRis a beautiful rectangle andarea(R) =k, thenarea(B_{k}) =k. And finally, ifarea(B_{k}) =k, thenarea(B_{k + 1}) >k, because ifR=B_{k}is beautiful, then eitherR_{k + 1}orC_{k + 1}is outside of the bounding boxB_{k}. Without loss of generality let it beR_{k + 1}. It follows thatk+ 1 is the first contestant at rowR_{k + 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 columnj. 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 obtainH+Wcandidates on the beautiful rectangles inO(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 .

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)).

Can you explain more on how it can be improved?

Would 10^7 segtree operations really pass?

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

B_{k}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 boxB_{k}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 inO(HW) and build an array stating ifB_{k}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`

inO(|a-b|).how can this pass in TL ? isnt it O(q*HW) ?

THe thing is you first do $$$O(HW)$$$ to compute all good prefixes (the ones which form a rectangle) when you do a swap $$$O(|a-b|)$$$ only $$$10,000$$$ prefixes can change and hence you only need to check those to update your total count of good prefixes and answer the query.

I am talking about the 20pnts stask. there, the (|a-b|) = 10K constraint was not there.

Oh, I see. It is right it doesnt work for the 20pts, I might have missed that. For the 20 points the number of rectangles is less than 4000 and you can compute them iteratively starting from the 1x1 rectangle and then expanding it to include the [MEX](https://en.wikipedia.org/wiki/Mex_(mathematics)) of the current rectangle. For that you only need to have the MIN in each column and each row which can be updated on every update.

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

Read the editorial at the official IOI website.

LooOoOoOOOooOoLooOooOooOooL. LMAO. ROFL.

Are you even too lazy to google that?

nopeeeee. i attemp many times but i don't find :D

I tried solving the fifth subtask of the problem seats (H = 1), but after reading the editorial I cannot understand how to use the lazy propagation segment tree to solve this. Can someone explain little bit on how to do this. Thanks in advance.

I can try this but I'm not sure if it is correct. Let's color cells which contains numbers 1 — x black others are white. Condition for this to be beautiful rectangle is that the (number of white cells which are adjacent to black cells should be <= 2). We have to maintain this value for each prefix.

Building : Let current number be 'x' and its position be 'pos'. Consider three case — both neighbour cells are black or one of them is black or none of them is black. For 1st case subtract 2. For 2nd case do nothing. For 3rd case add 2 to prefix 1-x.

Updates : Let two values that are swapped are 'sm' and 'lg'. sm is smaller of them. Consider 'sm' cell. Let its initial neighbours be val_11, val_12. If val_11 is greater than 'sm' subtract 1 from prefix(1,val_11). Same of val_12. Let its final neighbours be val_21, val_22. If they are greater than 'sm' add +1 to their prefixes. Do the same for larger value 'lg'. Update prefix (1-sm) & (1-lg) seperately.

Query : Check how many prefixes follow to above condition. You can easily check necessity and sufficiency of the condition.

Thank you for your reply, just to ask, in your update function by val_11 and val_12 do you mean the left and right neighbours of the current position?

Yes.