시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 13 | 10 | 9 | 75.000% |
You have $n$ black ants in your terrarium, and the $i$-th black ant lives at coordinate $(a_i, b_i)$.
Each day for the next $m$ days, you will buy a new ant for your terrarium. You are only buying white ants, and the $i$-th white ant that you are buying will live at coordinate $(x_i, y_i)$.
Each day, you feed some of your insects. If you feed an insect, the insect will not be hungry in that day. If the $i$-th white ant is hungry and the $j$-th black ant is hungry, and $x_i \geq a_j$ and $y_i \geq b_j$, they will fight. Find, for each day, the smallest number of ants to feed such that there are no fights.
The first line contains one integer $n$ ($1 \leq n \leq 100\,000$): the number of black ants in your terrarium.
Each of the next $n$ lines contains the description of black ants. The $i$-th of them contain two integers, $a_i, b_i$ ($0 \leq a_i, b_i \leq 100\,000$).
The next line contains one integer $m$ ($1 \leq m \leq 100\,000$): the number of days in which you are going to buy new white ants.
Each of the next $m$ lines contains the description of white ants in the order you buy them, such that the $i$-th of them contains two integers, $x_i, y_i$ ($0 \leq x_i, y_i \leq 100\,000$).
Note that different ants can live at points with the same coordinates.
Print $m$ integers, such that the $i$-th of them equals the smallest number of ants that you should feed to avoid fights among the black ants $1,2,\ldots,n$ and the white ants $1,2,\ldots,i$.
3 0 0 1 1 2 2 4 0 0 1 1 0 0 3 3
1 2 2 3