Chef has a New Kitchen
All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
Chef recently bought a new kitchen. This kitchen is huge! It is rectangular in shape with dimensions W × H, where W is the width and H is the height, both in meters. The kitchen is divided into a grid with W * H individual cells, each of size (1 meter) × (1 meter), and each cell is identified by two integers (x, y) denoting the column and row number of the cell, respectively (1 ≤ x ≤ W and 1 ≤ y ≤ H).
Chef has recently become lazy so instead of walking through his kitchen to work, he just sits forever at his chair located at (xC, yC). However, he sometimes needs to inspect individual locations (for example, to check if his personnel have become lazy too!). Instead of walking towards that location, he just uses a bunch of cheap robots with cameras. These robots are so cheap that Chef has an infinitely many number of them. However, their cheap parts pose a few severe limitations:
- Each robot can only move forward towards the direction it faces, and can only face a direction parallel to one of the walls of the rectangular kitchen.
- Each robot can only turn at 90 degree angles.
- Each robot can only turn at most once.
Note that a robot starts at Chef's location.
There is no problem initially in all of this, because all cells are reachable from Chef's location (xC, yC). However, when the appliances arrive and are installed in the kitchen, some cells cease to be reachable with a robot (because cheap robots cannot pass through appliances!).
Initially, the kitchen is empty, except for his chair. There are N appliances to be installed. Each appliance has dimensions (1 meter) × (1 meter) and occupies exactly one cell. The ith appliance to be installed in chronological order will be installed in (xi, yi). Now, after the addition of each appliance, Chef wants to know how many cells are still reachable with a robot!
The first line of the input contains five integers W, H, xC, yC, N separated by spaces, denoting the dimensions of Chef's new kitchen W × H, the location of Chef's chair (xC, yC), and number of appliances to add.
The next N lines contain information about the appliances. The ith line (after the first line) contains two integers xi and yi, where (xi, yi) is the location of the ith appliance.
Output N lines, where the ith line contains the number of reachable locations after adding the first i appliances.
- 1 ≤ N ≤ 105
- 1 ≤ W, H ≤ 105
- 1 ≤ xC, xi ≤ W
- 1 ≤ yC, yi ≤ H
- No two appliances occupy the same position, and no appliance occupies Chef's position.
20 10 4 3 5 6 5 7 4 8 4 9 3 4 2Output:
199 197 195 159 133
The following image illustrates the states of the kitchen after all appliances have been added.
|Tags||kevinsogo, range, range-trees, snck15fl, sqrt-decomp|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.