Cod sursa(job #2809196)

Utilizator rapidu36Victor Manz rapidu36 Data 26 noiembrie 2021 11:33:43
Problema Struti Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <deque>
#include <queue>

using namespace std;

const int N = 1e6;

int v[N];

int main()
{
    ifstream in("secvdist.in");
    ofstream out("secvdist.out");
    int n, k;
    size_t lmax = 0;
    deque <int> dqmin, dqmax;
    queue <int> q;
    in >> n >> k;
    for (int i = 0; i < n; i++)
    {
        in >> v[i];
        q.push(i);///i face parte din secventa curenta

        ///pentru a actualiza rez asociate (min si max) il adaug pe i in deque-uri
        while (!dqmin.empty() && v[dqmin.back()] >= v[q.back()])
        {
            dqmin.pop_back();
        }
        dqmin.push_back(q.back());

        while (!dqmax.empty() && v[dqmax.back()] <= v[q.back()])
        {
            dqmax.pop_back();
        }
        dqmax.push_back(q.back());

        ///cat timp secv retinuta in q nu e buna elimin elemente din stanga
        while (v[dqmax.front()] - v[dqmin.front()] > k)
        {///nu e necesar sa verific ca q, dqmin si dqmax nu sunt vide datorita lui i care va ramane la final in toate
            if (dqmin.front() == q.front())///elimin din stanga dqmin daca e cazul
            {
                dqmin.pop_front();
            }
            if (dqmax.front() == q.front())///elimin din stanga dqmax daca e cazul
            {
                dqmax.pop_front();
            }
            q.pop();
        }
        lmax = max(lmax, q.size());
    }
    out << lmax;
    in.close();
    out.close();
    return 0;
}