CVJETICI - Cvjetici

On a faraway planet, strange plants with two stems can be found. Every plant on the planet can be described by three numbers: the x-coordinates of the stems L and R, and the height H at which the stems are connect. The image depicts a plant with L=2, R=5 and H=4.

Every day a new plant grows on the planet. The plant that grows on day 1 is of height 1, and every subsequent plant is one higher than the previous one.

When a stem of a new plant intersects the horizontal segment of another plant, a small flower grows (if one wasn't there already). If segments merely touch in a point, a flower will not grow there. The following images are a visualization of the first example.

Write a program that, given the coordinates of all plants, calculates the number of new flower every day.


The first line contains an integer N (1 ≤ N ≤ 100 000), the number of days.

Each of the following N lines contains two integers L and R (1 ≤ L < R ≤ 100 000), the coordinates of the stems of a plant.


Output N lines, the number of new flowers after each plant grows.


1 4
3 7
1 6
2 6


1 3
3 5
3 9
2 4
3 8


hide comments
luka_: 2019-11-24 17:14:00

I agree with vlatko's comment

Last edit: 2019-11-24 17:22:29
vlatko: 2019-05-25 10:00:13

I agree with linkret's comment

ivanmilinovic: 2019-03-29 20:30:40

Very easy problem ac in 1 go

gabrijel: 2019-03-27 23:46:43

I had the same problem as fabijanb, but then I remembered splay tree and quickly got AC (in 1 go ofc)

fabijanb: 2019-03-27 21:49:37

any help please, I am really stuck with this problem for 13 days already, starting to give up

linkret: 2019-03-27 16:14:29

this task reminds me of the flower "jaglac", which is edible and quite delicious

shahwat: 2018-08-10 07:36:41

@imperfectboy, there will be no case where L == R. Read the problem statement carefully.

kspoj: 2017-12-19 18:00:11

Seg Tree :D :D

imperfectboy: 2017-10-16 03:46:07

1WA !!! don't forget to consider L=R case !!!

kejzak: 2015-12-07 16:03:37

all works except source limit..

Added by:Race with time
Time limit:0.203s-0.406s
Source limit:2000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO PERL6
Resource:COCI 2008/2009 - Croatian Regional