1022 Minuni

[•pauldb]

Aici puteți discuta despre problema Minuni.

Problema a fost adăugată de Andrei Antonescu.

[•repp4radu]

Salut!

Se poate obtine la problema asta 100 folosind solutia cu arbori de intervale in O(M * log M)? Eu iau 80 de puncte cu TLE pe ultimele 2 teste.

[•wefgef]

Am schimbat limita la 0.5

[•repp4radu]

A intrat acum. Multumesc! 

[•razvan.popa]

De ce o solutie cu set-uri care cauta la fiecare query pentru muchia curenta (x -> y), o muchie pusa anterior (a -> b) cu a maxim (a < x) nu este corecta?

[•dicu_daria]

De ce o solutie cu set-uri care cauta la fiecare query pentru muchia curenta (x -> y), o muchie pusa anterior (a -> b) cu a maxim (a < x) nu este corecta?

Gandeste-te ca poti avea query-uri de forma:
1 10
2 3
5 7

Daca ai cauta pentru al treilea query muchia cu a maxim, atunci rezultatul ar fi 2->3, ceea ce nu e corect pentru ca tu ai nevoie de o muchie care cuprinde intervalul (5, 7), muchia asta fiind 1->10.