|
Titlul: 3273. Order Statistic Set Scris de: Pirtoaca George Sebastian din Iulie 25, 2014, 19:10:49 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. Titlul: Răspuns: 3273. Order Statistic Set Scris de: Adrian Budau din Iulie 26, 2014, 12:06:31 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).
Titlul: Răspuns: 3273. Order Statistic Set Scris de: Pirtoaca George Sebastian din Iulie 28, 2014, 15:10:25 Mulțumesc pentru indicație. Cu treap-uri nu intra în nici un fel. Am reușit cu AINT-uri.
Titlul: Răspuns: 3273. Order Statistic Set Scris de: Alexandru Valeanu din Iulie 28, 2014, 23:03:00 Se poate si cu treap-uri dar trebuie sa citesti/afisezi cu scanf/printf.
Titlul: Răspuns: 3273. Order Statistic Set Scris de: Cosmin Rusu din Octombrie 17, 2014, 22:25:16 Depinde de implementare, mie mi-a intrat cu Treap-uri folosind stream-uri.
Linia asta e magica: Cod: cin.sync_with_stdio(false); |