Zadanie temperatura - problem

Question

Witam, napisałem kod z gąsienicą i kolejką monotoniczną, i gdy wrzucamy do szkopuła, to w niektórych testach przekracza on limit czasowy, co dziwne bo powinno wchodzić czasowo, najwyraźniej coś przegapiłem. Byłbym wdzięczny jakby ktoś mi wytłumaczył co jest nie tak, i czemu on jest za wolny.https://szkopul.edu.pl/problemset/problem/6sGsrkO-SrmtogJ7u3RIOj3f/site/?key=statement

#include <iostream>
#include <deque>
#include <utility>
#include <vector>
#include <cstdio>

using namespace std;

struct para {
    int first;
    int second;
} ;


deque<pair<int,int>> kolejka;
para tab[1000000+5];

void push_(int x,int idx){
    while(!kolejka.empty() && kolejka.back().first <= x)
        kolejka.pop_back();
    
    kolejka.push_back(make_pair(x,idx));
}

void pop_(int idx){
    if(!kolejka.empty() && kolejka.front().second == idx)
        kolejka.pop_front();
}

int get_maximum_(){
    return kolejka.front().first;;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;

    for(int i=0;i<n;++i){
        cin >> tab[i].first;
        cin >> tab[i].second;
    }
    push_(-1e9-5,-1);
    int l=0,r=0;
    int wynik=1;
    while(r < n){
        while(get_maximum_() > tab[r].second){
            pop_(l);
            ++l;
        }
        if(get_maximum_() <= tab[r].second){
            wynik = max(wynik,r - l + 1);
            push_(tab[r].first,r);
        }
        
        ++r;
    }
    printf("%d",wynik);

    return 0;
}

 

Comments

Tak nawiasem. Po co definiujesz strukturę para, skoro w kolejce i tak używasz std::pair?

Answer 1

W funkcji push powinno być < zamiast <= to napewno.

Comments

Rzeczywiście, ale i tak to nie chce wejść

Answer 2

Na początku analizowałem złożoność obliczeniową zaprezentowanego algorytmu i zatrzymałem się na tym konstrukcie:

while(get_maximum_() > tab[r].second){
   pop_(l);
   ++l;
}

Rozwijając ten kod otrzymujemy coś takiego:

while(kolejka.front().first > tab[r].second) {
   // funkcja pop_
   if(!kolejka.empty() && kolejka.front().second == l)
        kolejka.pop_front();
   ++l;
}

Generalnie program jest dla mnie bardzo ciężki w analizie przez enigmatyczne nazwy zmiennych ("l"), ale udało mi się wprowadzić program w bardzo długie czasy wykonania, dostarczając po prostu zera. Dając takie dane jak poniżej, program zamyka się w tej pętli, nie będąc w stanie zdjąć elementów ze stosu, bo l jest już daleko większe niż 0. 

0: 1 5 
1: 4 8 
2: 2 5 
3: 6 8 
4: 0 0 
5: 0 0 

Udało mi się również zrobić to z innymi liczbami (1, 5, -100). Program ewidentnie nie lubi dwóch następujących po sobie niskich wyników. 

 

Generalnie program jest wykonany dość złożenie obliczeniowo i wydaje mi się, że jego wykonanie może nawet zająć O(n^2) w najbardziej pesymistycznym momencie. Proponowałbym wersję, bez jakiejkolwiek pamięci w postaci listy/kolejki. 

Comments

Ciężko zaproponowac wersję bez kolejki / listy, bo nie da się dostać 100pkt bez tego. (chyba że chcesz zrobić listę/kolejkę na vectorze, ale to nie ma sensu).

---

=== EDIT ===

Jednak źle zrozumiałem zadanie, ale treść komentarza zostawiam nie zmienioną.

===

O ile dobrze rozumiem zadanie, to:

• Dany jest ciąg n, który reprezentuje kolejne dni pomiaru temperatury,
• Dana jest relacja n-1 ►n, która zwraca prawde, gdy temperatura dnia poprzedniego była niższa lub równa w dniu n. 
• Zwróć liczbę elementów, w których relacja ► była nieprzerwana najdłużej. 

Aby to zrealizować potrzebujemy trzymać tylko n i n-1 oraz aktualną liczbę dni o niemalejącej temperaturze oraz najdłuższy dotychczasowy rekord dni o niemalejącej temperaturze. 

Z tego co widzę na przykładzie relacja ► jest w rzeczywistości sprawdzeniem, czy najniższa temperatura dnia poprzedniego jest niższa od temperatury maksymalnej dnia n.

Dlatego tez nie widzę potrzeby trzymania wszystkich danych wejściowych w pamięci. Ale możliwe, że "szkopuł" nakłada jakieś ograniczenia, lub źle przeczytałem zadanie, choć nie wydaje mi się :). 

---

Może się zdażyć, że w dniach i...j temperatura mogła być niemalejąca, w dniach i..(j+1) nie, a w dniach (i+1)...(j+1) tak. Wtedy sprawdzanie dwóch ostatnich dni nie wystarczy

---

@MikDal, A kolejka monotoniczna wraz z gąsienicą nie ma złożoności O(n) ?

---

Działa w O(n), ale najwidoczniej program wiesza się na nieskończonej petli while. Musisz poprawić warunki w pętli

---

@Whistleroosh, przysiadłem do tego na spokojnie, masz rację, pomyliłem się, nie można tego zadania wykonać w O(n). Także moje założenie powyżej jest błędne. 

@Dani, co do samej kolejki z gąsienicą to podaje się, że ma złożoności O(n). Niektóre źródła (np. to Informatyka. Konkursy i algorytmy. (oki.org.pl)) podają O(2n), co podoba mi się bardziej. 

---

Tak kolejka monotonniczna wykona pesymistycznie 2N operacji, bo każdy element maksymalnie raz dodasz i raz usuniesz. Ale 2N to O(N).

---

int get_maximum_(){
    if(kolejka.empty())
       return -1e9-5;
    return kolejka.front().first;;
}

W końcu znalazłem problem. Mianowicie trzeba było w otrzymywaniu maksa uwzględnić przypadek pustej kolejki, i teraz wchodzi na 100 pkt. Dziękuję wszystkim za poświęcony czas!