Zwykle w Potyczkach bywają strasznie małe limity czasu, a w tej rundzie były olbrzymie, w porównaniu! A ja tak optymalizowałem mój kod :)

Moje najgorsze czasy:
cia 0.07s/3.00s
muz 0.41s/3.00s
ple 0.33s/16.00s
fio 0.64s/6.00s

Nie dziwię się że optymalizowałeś, po tylu maksach z rzędu presja aby nie uronić ani punkta na TLE musi być zabójcza ;)

W muzeum moim zdaniem wcale nie było wysokiego limitu. Ja miałem 2.63/3.00, a Smu 2.01/3.00, a obaj mieliśmy wzorcową złożoność i ja bym się bardzo zdziwił, jakby nie weszło. Choć w ple rzeczywiście jakieś strasznie wielkie.

Pewnie używacie STL-owego set'a - ja go unikałem, bo on wolny, alokuje i zwalnia pamięć przy każdej operacji. Może jakby w nim podmienić allocator na jakiś lepszy to by szybciej działał.

Ja nie miałem, żadnego seta w muz, przeskalowywałem sortem i oprócz tego miałem tylko jedno drzewo przedziałowe. Jestem jednak świadom, że mogłem trochę stałą zbić.

Za to seta użyłem w drużynach i oddałem tym samy 2 punkty :(

A co do limitów czasowych to w cia powinny być według mnie bardziej zróżnicowane w obrębie jednego k, żeby rozróżnić rozwiązania, które to robią trochę za wolno od rozwiązań, które tego wcale nie są w stanie przeliczyć. (Trochę smutne, że moje rozwiązanie które działa niewiele dłużej niż te 3 sekundy dostaje 6 punktów).

I ocenianie w kol, też mi się trochę nie podobało. Powinno być tak że jest zawsze 100 kompów tylko dane rosną. A tak jak teraz to wygląda jakby każdy z testów był prawie max testem i jakby rozwiązanie 4-5 razy za wolne miało dostać 1/10.

Ja w muz miałem rekurencyjne drzewo przedziałowe. To ile razy je pisałem można policzyć na palcach jednej ręki (jednak ta liczba zwiększyła się dzień wcześniej w trakcie pisania nawet dwuwymiarowego drzewa rekurencyjnego w PLE, które i tak okazało się blefem :P). Rekurencyjne przedziałówki są wolniejsze, ale niektórych zadań się na iteracyjnych nie da zrobić albo jest to dużo mniej wygodne (takich ala bit aktualności mówiący "wszystko pode mną jest bez sensu"), a to był ten przypadek dla mnie.
Moje drzewko musiało wspierać operacje
1) Dodaj x na przedziale
2) Maksuj z x na przedziale
3) Czytaj w punkcie
A co do kol, to uwaga Marcina wydaje się całkiem trafna.

Ja w muz wykorzystuję to, że ciąg jest rosnący i trzymam tylko miejsca w których on rośnie. Drzewko wspiera mi operację znajdowania następnego takiego miejsca. Moje niskie czasy wynikają też po części z własnej szybszej implementacji wczytywania liczb z wejścia.

Tak get[U]Int() bazowany o buf[64K] + syscall read() + własny getChar()/ungetChar() rządzi, nie mam pojęcia czemu i stdio i iostream są tak cholernie wolne.

Ja mam MUZ na secie par longlongów, wczytuję scanfem, i działa mi 0.56s.