Cod sursa(job #2040053)

Utilizator stefanst77Luca Stefan Ioan stefanst77 Data 15 octombrie 2017 13:11:30
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <bits/stdc++.h>
#define lung 500007
using namespace std;

ifstream fin ("secventa.in");
ofstream fout ("secventa.out");

int n, k, m;
int a[lung];
char c[6*lung];
deque <int> q;
int pozinceput, pozfinal, valmax;

int Nr(int &i)
{
    int x=0;
    while (c[i]>='0' && c[i]<='9')
        x=x*10+c[i++]-'0';
    return x;
}

void Citire()
{
    fin >> n >> k;
    fin.get();
    fin.getline(c, 6*lung);

    int semn;
    for (int i=0; c[i]!=0;)
    {
        if (c[i]=='-')
        {
            semn=-1;
            i++;
        }
        else semn=1;

        a[++m]=semn*Nr(i);

        if (c[i]==' ') i++;
    }
}

void Rezolvare()
{
    int i, x;
    /// adaugam pana la k in vector valorile cele mai mare, in ordine cresc.
    for (i=1; i<=k; i++)
    {
        x=a[i];
        while (!q.empty() && x<a[q.back()])
            q.pop_back();
        q.push_back(i);
    }
    ///initializam
    valmax=a[q.front()];
    pozfinal=q.back();
    pozinceput=pozfinal - k + 1;

    for (i=k+1; i<=n; i++)
    {
        ///actualizam maximul
        x=a[i];
        while (!q.empty() && x<a[q.back()])
            q.pop_back();
        q.push_back(i);

        /// verificam validarea
        if (q.front() < i-k+1 && !q.empty())
            q.pop_front();

        /// actualizam raspunsurile
        if (valmax < a[q.front()])
        {
            valmax=a[q.front()];
            pozfinal=q.back();
            pozinceput = pozfinal - k + 1;
        }
    }
}

int main()
{
    Citire();
    Rezolvare();
    fout << pozinceput << " " << pozfinal << " " << valmax << "\n";

    fin.close();
    fout.close();
    return 0;
}