[c++ i algorytmika] Jak znaleźć szukane wartosći!

Witam! Mam do rozwiązania taki problem:
Mam n punktów. Każdy punkt opisany jest jako jego indeks oraz jego wysokość. Teraz muszę dla każdego punktu znaleźć punkt o największej wysokości na lewo od niego i punkt o najwyższej wysokości na prawo od niego. Może podam przykład:
5 <-liczba punktów
1 <-1.punkt
3 <-2.punkt
2 <-3.punkt
4 <-4.punkt
3 <-5.punkt
Program powinien wypisać:
1 4 <- dla 1. punktu max na lewo to 1, max na prawo to 4
3 4 <- dla 2. punktu max na lewo to 3, max na prawo to 4 (dany punkt - wysokość - też jest liczony jako na lewo i prawo)
3 4 itd.
4 4
4 3

Ja sobie realizuję to tak, że mam strukturę, w której zapisuję indeks punktu, jego wysokość, max. wys. na lewo i max. wys. na prawo. Potem wczytuję dane i robię 2 pętle:
'if(tab[i].wys > lewo)
lewo= tab[i].wys;
tab[i].lewo = maxlewo;'
i analogicznie drugą pętle na prawo(tab to tablica punktów). Po prostu lecę raz z lewej do prawej, zapamiętuje maxa i dla każdego punktu zapamiętuję max. Potem lecę od prawej do lewej i robię analogicznie to co wyżej.
Problem jest w tym, że jest to bardzo wolne, tym bardziej, że ilość punktów może być równa milion, a wysokość 10^9.

Zatem bardzo proszę o podpowiedzenie mi, jak można to zrealizować szybciej? Wiem, że na pewno się da ;)

Pozdrawiam i gdyby coś było niejasne jeśli chodzi o zadanie to proszę pisać.

lokery

czyli na razie masz O(n^2) jeśli dobrze rozumiem

proponuje zrobić O(n) a dokładniej jakieś 2n

left[0]=val[0]
for i=1..n
	if left[i-1]>val[i]
		then left[i]=left[i-1]
		else left[i]=val[i]

i analogicznie dla prawego

Zrobiłem program wg twojego algorytmu, program daje prawidłowe odpowiedzi, ale nadal jest bardzo wolny! Jest wprawdzie zmiana w stosunku do tamtej wersji O(n^2), ale to co ty podałeś to chyba O(n) nie jest. Na pewno da się to bardziej przyspieszyć, ale jak? Chyba trzeba wykorzystać może jakiś zupełnie inny algorytm?

lokery napisał(a)

ale to co ty podałeś to chyba O(n) nie jest.
a czemu nie jest? :>

innego pomysłu na szybszy algorytm nie mam, tym bardziej jeśli rekordów miałoby być tak dużo...

a do czego potrzebujesz te punkty?

Robię zadanko.

Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita n (1 ¬ n ¬ 1 000 000) ozna-
czająca długość pasma górskiego. W każdym z następnych n wierszy znajduje się po jednej liczbie całkowitej
wi (1 ¬ wi ¬ 1 000 000 000) oznaczającej wysokość i-tego punktu podziału. Punkty te podane są w kolejności
z zachodu na wschód.
W testach wartych przynajmniej 40% punktów zachodzi dodatkowy warunek n ¬ 10 000.
Wyjście
Twój program powinien wypisać na standardowe wyjście dokładnie n wierszy, odpowiadających kolejnym
punktom podziału (w kolejności z zachodu na wschód). W każdym z tych wierszy powinny znaleźć się dwie
liczby całkowite ai oraz bi oddzielone pojedynczym odstępem — wysokość najwyższego punktu podziału na
zachód od punktu i oraz na wschód od niego. W przypadku, gdy na zachód od punktu i nie ma szczytu
wyższego niż wi, przyjmujemy ai = wi. Podobnie, jeśli na wschód od punktu i nie ma szczytu wyższego niż
wi, to przyjmujemy bi = wi.

Zadania masz wykonać samodzielnie. Moderatorów proszę o usunięcie. (Zadanie z OIG)

To nie znaczy, że ktoś nie może podsunąć pomysłów na algorytm. Nie proszę o żaden gotowy kod...

Rozwiązania zespołowe, niesamodzielne, niezgodne z "Zasadami organizacji zawodów" lub takie, co do których nie można ustalić autorstwa, nie będą oceniane. W przypadku uznania przez Komitet pracy za niesamodzielną lub zespołową zawodnicy mogą zostać zdyskwalifikowani.
Zadanie polega głównie na wymyśleniu algorytmu. Napisanie programu to pikuś. Pan Pikuś.

przy czym mogą zwracać się z pytaniami do innych osób (także nauczycieli) w celu wyjaśnienia wątpliwości.

Wątpliwości, a nie podpowiedzi.

Mam wątpliwości, czy moje rozwiązanie o złożoności O(n^2) nie jest za wolne. Rozwiązanie podane wyżej o złożoności O(n) również działa bardzo wolno. Zatem czy nie mógłby ktoś być tak miły, by rozwiać moje wątpliwości i podpowiedzieć jak wymyślić lepszy algorytm, bym już nie miał wątpliwości?

Rozwiązanie jest za wolne. Wystarczyło wejść na forum siogim żeby zobaczyć jakie wyniki mają inne programy. Wątpliwości rozwiane, a na podpowiedzi nie licz.

Dobra koleś, wygrałeś ;)
Kilka usprawnień technicznych i mam czas dla testu 5. 0,81s. Ujdzie w tłumie, max i tak mi niepotrzebny.