ZQUERY2 - Intersection Query
Considering a set of segments. At the beginning, the set is totally empty.
There are N operations: insert or erase a vertical (or horizontal) segment and then you have to compute how many intersections are there.
There is no two same type of segments that share a common point in the set.
Input
The first line contains N (1 ≤ N ≤ 105) - the number of operations.
The following N lines describe the operations:
- 1 X1 Y1 X2 Y2: insert a segment whose two endpoints are (X1, Y1) and (X2, Y2) to the set. (|X1|, |Y1|, |X2|, |Y2| ≤ 109)
- 2 K: erase the K-th oldest segment from the set. (1 ≤ K ≤ current size of the set)
Output
For each query, print the number of intersections of the line segments in the set after processing the operation in one line.
Example
Input: 10 1 -1 0 -2 0 1 2 -2 0 -2 1 1 1 1 -3 2 1 1 6 -2 5 -2 2 3 1 2 -2 2 -6 1 -4 -3 -5 -3 1 3 -4 -1 -4 2 2 Output: 0 0 1 1 1 1 2 2 3 2
UPD (1/30/2015): Increase time limit from 2s to 5s. My C++ solution (unoptimized) runs in about 7 seconds.
hide comments
Rishav Goyal:
2016-08-22 13:38:14
@author: will it pass nlogn^3?
|
Added by: | What Does The Fox Say? |
Date: | 2015-01-07 |
Time limit: | 5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 JS-MONKEY |