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

1 | tourist | 3539 |

2 | Radewoosh | 3464 |

3 | V--o_o--V | 3338 |

4 | Um_nik | 3307 |

5 | Petr | 3297 |

6 | ecnerwala | 3282 |

7 | LHiC | 3266 |

8 | wxhtxdy | 3264 |

9 | Vn_nV | 3182 |

10 | xyz111 | 3147 |

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

1 | Radewoosh | 207 |

2 | Errichto | 176 |

3 | neal | 159 |

4 | Ashishgup | 158 |

5 | Petr | 157 |

5 | PikMike | 157 |

7 | majk | 156 |

7 | rng_58 | 156 |

9 | Um_nik | 154 |

9 | 300iq | 154 |

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/16/2019 22:29:09 (d2).

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