Historyjka

W komunikatorze K, ze scentralizowanym serwerem, głównym zadaniem serwera jest rozwiązywanie nicków na adresy komputerów (ipv4+port) użytkowników. Ich komunikatory potem już łączą się ze sobą bez użycia serwera.

Serwer do obsługi zapytań korzysta wewnętrznie z drzewa BST (z porządkiem leksykograficznym względem nick'ów). Dzięki temu może w dowolnym momencie szybko dodać kolejnych użytkowników do systemu.

O kształcie drzewa BST decyduje kolejność zgłoszeń. Główni programiści zastanawiają się czy nie warto poczynić optymalizacji. W tym celu zostałaś/eś poproszona/y o dokonanie statystyk.

Problem

Mając dostępne logi ułożone w kolejności zgodnej z tą w jakiej użytkownicy pojawiali się w systemie, oraz ilość odpytań do o ich nicka w ostatnim miesiącu, określić jakie byłoby obciążenie wspomnianej struktury danych w zależności od sposobu konstrukcji drzewa.

Zbuduj trzy drzewa BST, podając elementy do operacji Insert():

  • TreeFromMin - w kolejności "od najmniejszej" ilości odpytań.

  • TreeAsInput - w kolejności zgodnej z danymi wejściowymi (czyli chronologią).

  • TreeFromMax - w kolejności "od największej" ilości odpytań.

W przypadku dwóch węzłów o tej samej ilości odpytań o kolejności decyduje porządek (odpowiednio do drzewa rosnący lub malejący) leksykograficzny nick’a.

Dla każdego drzewa policz ile w poprzednim miesiącu zostałoby odwiedzonych sumarycznie węzłów drzewa. Niech wyniki dla poszczególnych drzew będą FromMin, AsInput, FromMax.

Specyfikacja wejścia

Wiersze zawierają odpowiednio nick, adres ip+port, ilość odpytań z ostatniego miesiąca, oddzielone pojedynczym tabulatorem.

  • nick - do 16 znaków ze zbioru: a-z, A-Z, 0-9.

  • ip:port - cztery liczby <0;28-1> w zapisie dziesiętnym oddzielone kropką jako ip, a po nich dwukropek i numer portu <0; 216-1>

  • hits - ilość odwołań w ostatnim miesiącu <0;231-1>

Dane mogą być, ale nie muszą zakończone pustym wierszem. Dla każdego nick-a widnieje jeden wpis w logu. Sumaryczna ilość wierzy - n jest <1;1000000>.

Specyfikacja struktury

Komparator nicków w drzewie ma być zgodny z porządkiem leksykograficznym stosowanym przez komparator string w C++ na platformie testowej. (Więcej informacji w pliku komparator_cpp.html).

Specyfikacja wyjścia

Trzy linie, odpowiednio po trzy, dwie, jedną liczbę całkowitą.

W pierwszej linii odpowiednio trzy liczby:

  • FromMax AsInput FromMin

W drugiej, dwie różnice:

  • AsInput-FromMax FromMin-AsInput

W trzeciej, jedna różnica:

  • FromMin-FromMax

Porada implementacyjna

Przyjrzyj się na możliwe wielkości danych wejściowych i zastanów się nad odpowiednimi typami liczb do obliczeń arytmetycznych.

Limity

Pamięć: 400MB.

Przykłady

  • nicki i adresy ip:port osób zostały wymyślone, stąd możliwa zbieżność jest zupełnie przypadkowa

00.in

a       45.67.214.4:6723        10
b       56.25.67.123:12543      1000
d       56.23.78.213:3465       200
c       68.123.234.34:4343      1

00.out

1423    2614    3421
1191    807
1998

01.in

c       33.33.33.33:3333        3
i       99.99.99.99:9999        9
a       11.11.11.11:1111        1
d       44.44.44.44:4444        10
f       66.66.66.66:6666        5
b       22.22.22.22:2222        2
h       88.88.88.88:8888        8
g       77.77.77.77:7777        4
e       55.55.55.55:5555        7

01.out

145 178 261
33 83
116

02.in

a       45.67.214.4:6723        2147483645
h       23.213.23.56:3465       2147483640
e       73.158.223.142:3245     2147483643
b       56.25.67.123:12543      2147483647
g       26.63.28.123:6578       2147483641
d       56.23.78.213:3465       2147483646
c       68.123.234.34:4343      2147483644
f       67.23.435.123:2341      2147483642

02.out

55834574703 64424509310 73014443915
8589934607 8589934605
17179869212