Cod sursa(job #2036834)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 11 octombrie 2017 09:43:42
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <deque>
using namespace std;
int n, k, bmax, pos;
int A[5000010];
deque < int > D;
char s[4000003];

void citire()
{
    ifstream f("secventa.in");
    f>>n>>k;
    f.get();
    // PARSAREA FLUXULUI DE INTRARE
    f.getline(s, 4000001);
    int j = 0, sign;
    for (int i = 1; i <= n; i++)
    {
        sign = 1; A[i] = 0;
        if(s[j] == ' ') j++;
        if(s[j] == '-') { sign = -1; j++; }
        while(s[j] >= '0' && s[j] <= '9') { A[i] = A[i]*10 + (s[j] - '0'); j++; }
        A[i] *= sign;
    }
    f.close();
}

void rezolvare()
{
    int x;
    for(int i = 1; i <= k; ++i)
    {
        x = A[i];

        while (!D.empty() && x <= A[ D.back() ]) D.pop_back();

        D.push_back(i);
    }

    bmax = A[ D.front() ];
    pos = D.back();

    for (int i = k+1; i <= n; i++)
    {
        // Cat timp elementul curent este mai mic decat ultimul element din deque, eliminam pozitia ultimului element din deque
        while (!D.empty() && A[i] <= A[ D.back() ]) D.pop_back();
        // Adaugam pozitia elementului curent in deque
        D.push_back(i);
        // Daca elementul minim coincide cu cel de pe pozita i-k, ii eliminam pozitia din deque, deoarece acesta nu mai conteaza pentru pasii >= i
        if (D.front() < i-k+1) D.pop_front();
        // Afisam minimul, acesta aflandu-se in varful deque-ului
        if (i >= k && A[D.front()] > bmax)
        {
            bmax = A[D.front()];
            pos = i;
        }
    }
}

void afisare()
{
    ofstream g("secventa.out");
    g << pos-k+1 << ' ' << pos << ' ' << bmax << '\n';
    g.close();
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}