Flores
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 and
.
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.
Input
The first line contains an integer , the number of days.
Each of the following N lines contains two integers L and R , the coordinates of the stems of a plant.
Output
Output N lines, the number of new flowers after each plant grows.
Example Input
4
1 4
3 7
1 6
2 6Output
0
1
1
2Input
5
1 3
3 5
3 9
2 4
3 8Output
0
0
0
3
2
Comments
Brother cogiste mas de 60 pts porque los primeros casos de pruebas estan faciles y se les puede raspar bastante con Force Brute , pero para coger 100 pts tienes que tirar un ( ABI con Deferent Array ) o un ( Segment - tree con Lazy Propagation ). Si el tipo de problema es de Segment - tree es porque la solucion oficial es con este algoritmo.
Dice ser un problema de Segment Tree... pero no le apliqué eso y me salí con mas de 60 puntos ?
Muchas gracias a todos por la ayuda ✌?
El usuario Primervirgen no puede hacer comments en ningun problema, lo cual impide preguntar cualquier duda al resolver un ejercicio, si esto se le impuso como penalizacion por algun comentario ofensivo ya deberia haber cumplido su tiempo, ya que en la mayoria de sitios esto dura 48h. Si alguno de los admin lee esto por favor que se le remueva esta penalizacion, la presencia de la pagina o su orgullo no es mas importante que resolver problemas y promover el movimiento :)
Ese usuario fue penalizado por incumplir en reiteradas ocasiones los términos del sitio, recomendamos a todos una vez más que los lean. Si él lo desea debe enviar un correo a las direcciones de contacto del sitio para que los administradores reevalúen la penalización y le den una respuesta.
Gracias por responder, espero que se pueda solucionar el problema.