All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is working with the development of a new city Krewsko. He and other city planners are designing the transportation system of Krewsko. They are using Cartesian coordinates and Krewsko will only have roads that are parallel to either the x-axis or the y-axis.
It is clear that we need to add one set of traffic lights at every intersection of roads where a person has at least two other directions to continue their trip when arriving at the intersection. Your task is to count how many traffic light sets should be deployed. In particular, for each road you want to know how many traffic light sets will appear on that road.
Let's formalize how a road in the city is defined. A road is a segment on the plane with endpoints in Xi,1, Yi,1 and Xi,2, Yi,2 for ith line. You are guaranteed that each line segment is either a vertical line or a horizontal line. An intersection is a point that belongs to two line segments: one horizontal and another vertical. We guarantee that no two vertical lines will share a point and no two horizontal lines share a point.
You must put a set of lights at each intersection of a horizontal and a vertical line segment where the point of intersection is not an endpoint of both segments.
The first line of the input contains an integer N indicating number of roads.
The next N lines contain 4 integers each. The ith line contain Xi,1, Yi,1 and Xi,2, Yi,2.
The output consists of two lines. The first line contains a single integer indicating the number of sets of lights that will be used throughout all of Krewsko. The second line consists of N integers. The i'th such integer indicates the number of traffic light sets that will be deployed to the i'th road. There should be a single space between consecutive integers on this line.
- 1 ≤ N ≤ 105
- 1 ≤ Xi,1 ≤ 105
- 1 ≤ Yi,1 ≤ 105
- 1 ≤ Xi,2 ≤ 105
- 1 ≤ Yi,2 ≤ 105
- The length of each road is positive and each road will either be a horizontal line segment or a vertical line segment.
- Subtask #1 [40 points]: N ≤ 10000
- Subtask #2 [60 points]: No additional constraints
Input: 4 2 1 2 6 1 3 5 3 4 1 4 4 1 5 5 5 Output: 3 2 2 1 1
|Tags||cenadar, line-sweep, medium, nov16, segment-tree|
|Time Limit:||1 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.