Zadanie temperatura oi

Question

Witam rozwiązuję zadanie temperatura, napisałem kod jednak nie przechodzi wszystkich testów. Trzymałem x i sprawdzałem czy mieści się w przedziale. Szedłem w tym czasie gąsienicą.

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


pair<int,int> tab[1000*1000+5];

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;
    }
    int l=0,r=0;
    int x = -1e9 - 5;
    int maxs = 0;
    while(r < n){
        if(x < tab[r].first)
            x = tab[r].first;
        if(x <= tab[r].second)
            maxs = max(maxs, r - l + 1);
        else{
            l = r;
            x = tab[r].first;
        }
        ++r;
    }
    cout << maxs << '\n';
    return 0;
}

 

Answer 1

A co jak masz zmienna max z przedzialu [l, p] a przesuwasz l na l+1 i max się zmienia a ty go nie znasz.

Musisz dodać seta / kolejkę monotoniczna, ale z setem nie wiem czy wejdzie czasowo. Z kolejka monotoniczna da się w O(N) zrobić.