Szczegółowe omówienie zadania Widoczność:

Link do powyższego omówienia zadania Widoczność:
https://youtu.be/Z6gbU76W–M?t=2114

Link do treści zadania Widoczność:
https://ki.staszic.waw.pl/task.php?name=widocznosc

–
Zadanie Widoczność jest szkoleniowym zadaniem pokazującym zastosowanie kolejki monotonicznej w algorytmice:
https://youtu.be/Z6gbU76W–M?t=2881

Kod zadania Widoczność
https://youtu.be/Z6gbU76W–M?t=3723

Złożoność kolejki monotonicznej
https://youtu.be/Z6gbU76W–M?t=5284

Dlaczego kolejka monotoniczna?
https://youtu.be/Z6gbU76W–M?t=5430

–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625

–
Kod C++ programu Widoczność, który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 5e5 +10; //500 010

//  wartosc, numer
pair <int,int> max_wartosc[MAX_N];
int element_ostatni;

//A: Jesli na czubku stosu jest element wiekszy od nas to:
//   - czubek stosu nam zaslania swiat i go zwarcamy a konkretnie indeks elementu na czubku stosu
//   - wkladamy siebie na czubek stosu (moze my teraz bedziemy ograniczac nastepnemu) - jeszcze przez zworceniem czubka stosu
//B: Zdejmujemy mniejsze lub rowne nam elementy ze stosu
//    - one nas nie zalsaniaja
//    - w przyszlosci nie zaslonia nic nikomu bo mniejsze od nas i to my ewentualnie cos zaslonimy
//    - zdejmujemy elemety ze stosu az natrafimy na A: lub stos sie skonczy czyli C:
//C: Jesli jest pusty to wstawiamy siesbie do stosu i zwracamy -1
int ZnajdzOgraniczajacy (int akt_wartosc, int i) {
 while (element_ostatni >= 0) {
    if (akt_wartosc < max_wartosc[element_ostatni].first) {
       ++element_ostatni;
       max_wartosc[element_ostatni].first = akt_wartosc;
       max_wartosc[element_ostatni].second = i;
       return max_wartosc[element_ostatni-1].second;
    }
    --element_ostatni;
 }
//gdy element_ostatni jest -1
 element_ostatni = 0;
 max_wartosc[element_ostatni].first = akt_wartosc;
 max_wartosc[element_ostatni].second = i;
 return -1;	
}

int main(){
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 
 int liczba_elementow, akt_wartosc;
 int ograniczajacy;
 int i;

 cin >> liczba_elementow;

 element_ostatni = -1;
 for (i=1; i<=liczba_elementow; ++i) {
    cin >> akt_wartosc;
    ograniczajacy = ZnajdzOgraniczajacy(akt_wartosc,i);
    cout << ograniczajacy << "\n";
 }

 return 0;
}