3273. Order Statistic Set

[•SebiSebi]

Salut!

Am încercat să rezolv această problemă http://www.spoj.com/problems/ORDERSET/ utilizând Treap-uri în complexitate O(logN) respectiv O(log^2 DIFF) unde DIFF este diferența maximă posibilă între două valori din setul S (vine de la cautare binară). Iau TLE începând cu testul 7? Cum se poate rezolva mai repede răspunzând la query-uri online? Cu normalizare și AIB sau AINT iese în O(logN) pe ambele query-uri.

[•freak93]

Daca nu te deranjeaza O(N log MAXVAL) memorie ai putea sa incerci un arbore de intervale dinamic, adica in loc sa tii un vector il tii chiar ca un arbore, cu pointeri catre fii peste toate valorile posibile (de 1 la 1 miliard).

[•SebiSebi]

Mulțumesc pentru indicație. Cu treap-uri nu intra în nici un fel. Am reușit cu AINT-uri.

[•AlexandruValeanu]

Se poate si cu treap-uri dar trebuie sa citesti/afisezi cu scanf/printf.

[•CosminRusu]

Depinde de implementare, mie mi-a intrat cu Treap-uri folosind stream-uri.
Linia asta e magica:

Cod:

cin.sync_with_stdio(false);