All submissions for this problem are available.
Sherlock agrees to take the case Swati brought.
Immediately he starts working on it. His first step is to figure out the location where Swati might have lost her bag. Mr. Holmes have a secret underground group of detectives. One among them is Shubham. Now the city of Knitwille is such spread that it’s just a long single straight line road across which the entire city sprawls. So Swati must have travelled in this same long straight line road. Sherlock asks Shubham to trace back the locations where Swati must have stopped in the duration of her outing. Shubham brings up a list of points on the roads where Swati stopped during her outing.
Rest of the Sherlock’s underground team lead by Chatur is such spread onto the straight road that each of them have an operational region defined by a segment on the road. Such segments on the road maybe overlapping, non-overlapping or partially overlapping.
Atul, one of the top-most underground detective brings this list of regions of operations in the form of segments defined by a starting point and an ending point on the road (both inclusive).
So the step 2 is to figure out in how many of the operational regions, each of her location points lie.
The first line of the input contains two space separated integers K and L denoting number of regions and number of location points.
Next K lines contain two space separated integers xi and yi denoting the i-th region.
Next L lines contains L space-separated integers l1, l2, ..., lL denoting the location points.
The Output should contain a single line containing L space separated integers, i-th of which denotes the number of segments in which location li falls.
1 ≤ K, L ≤ 5 x 104
-108 ≤ xi ≤ yi ≤ 108
Input: 2 3 -4 3 1 5 2 -3 4 Output: 2 1 1
Example case 1.
Location point 2 lies in two regions defined by [-4, 3] and [1, 5]. Point -3 falls in just one region [-4, 3] and point 4 also falls in just 1 region.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions