(Categoria _Structuri de date_, Autor _Xulescu_)

(toc){width: 25em}*{text-align:center} *Conţinut:*

(toc){width: 27em}*{text-align:center} *Conţinut:*

* 'Introducere':deque-si-aplicatii#introducere
* 'Operaţii':deque-si-aplicatii#operatii
* 'Aplicaţii':deque-si-aplicatii#aplicatii

** 'Problema 1: Book Pile (SGU)':deque-si-aplicatii#problema-1

** 'Problema 1: Book Pile (SGU)':deque-si-aplicatii#problema-1

** 'Problema 2: Şir':deque-si-aplicatii#problema-2

** 'Problema 3: Trans (ONI 2004)':deque-si-aplicatii#problema-3
** 'Problema 4: Otilia (.campion)':deque-si-aplicatii#problema-4
** 'Problema 5: Cut the Sequence (PKU)':deque-si-aplicatii#problema-5
** 'Problema 6: Bcrc (Stelele Informaticii 2006)':deque-si-aplicatii#problema-6

** 'Problema 3: Trans (ONI 2004)':deque-si-aplicatii#problema-3
** 'Problema 4: Otilia (.campion)':deque-si-aplicatii#problema-4
** 'Problema 5: Cut the Sequence (PKU)':deque-si-aplicatii#problema-5
** 'Problema 6: Bcrc (Stelele Informaticii 2006)':deque-si-aplicatii#problema-6

* 'Concluzii':deque-si-aplicatii#concluzii
* 'Probleme suplimentare':deque-si-aplicatii#probleme-suplimentare
* 'Bibliografie':deque-si-aplicatii#bibliografie

== code(cpp) |
#include <fstream>
#include <deque>

#include <vector>

#include <algorithm>

using namespace std;

const char iname[] = "sir.in";
const char oname[] = "sir.out";
 
typedef int (*PF)(const int& , const int& ) ;
 
deque <int> min_deq, max_deq;

typedef int (*PF)(const int , const int ) ;

vector <int> V;

int V[100005];  deque <int> min_deq, max_deq;

int min_fct(const int& a, const int& b) { return a < b; }

int min_fct(const int a, const int b) { return a < b; }

int max_fct(const int& a, const int& b) { return a > b; }

int max_fct(const int a, const int b) { return a > b; }

void push_in(deque <int>& deq, int& p, PF compare) {

void push_in(deque <int>& deq, const int p, PF compare) {

    for (; !deq.empty() && compare(V[p], V[deq.back()]); deq.pop_back()) ;
    deq.push_back(p);
}

int query(deque <int>& deq, const int& first) {
    for (; !deq.empty() && deq.front() <= first; deq.pop_front()) ;

int query(deque <int>& deq, const int j) {
    for (; !deq.empty() && deq.front() <= j; deq.pop_front()) ;

    return V[deq.front()];
}
int main(void)
{

    ifstream in(iname);  ofstream out(oname);

    ifstream in("sir.in");  ofstream out("sir.out");

    int N, X, Y, Z;

    int length = 0, start = 0, stop = 0;
 
    int j = 0;

    int length = 0, start = 0, stop = 0, j = 0;

    in >> N >> X >> Y >> Z;

    V.resize(N + 1);

    for (int i = 1; i <= N; ++ i) {
        in >> V[i];

        // (j, i] este intervalul candidat la solutia pentru pozitia i;

        push_in(min_deq, i, min_fct);
        push_in(max_deq, i, max_fct);

        while ((j < i - Y || query(max_deq, j) - query(min_deq, j) > Z) && j < i - X)
            j ++;

        // (j, i] este intervalul candidat la solutia pentru pozitia i;

        if (j <= i - X) if (query(max_deq, j) - query(min_deq, j) <= Z)
            if (i - j >= length)
                length = i - j, start = j + 1, stop = i;
    }

 
    if (length > 0)
        out << length << " " << start << " " << stop << "\n";
    else
        out << -1;
 

    length > 0 ? cout << length << " " << start << " " << stop : cout << -1;

    in.close(), out.close();
    return 0;
}

==
Complexitatea finală va fi $O(N)$.