Cod sursa(job #1997991)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 6 iulie 2017 01:05:58
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <climits>
#include <cstring>
using namespace std;

int x[500001], Deque[500001];
int n, k, i, Max, Front, Back, start, stop, p, semn, l;
char s[3500001];

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

    fin>>n>>k;
    fin.get();
    fin.getline(s, 3500001);
    int l=strlen(s); p=1;
    for(i=0; i<l; ++i)
    {
        semn=1;
        if(s[i]=='-') semn=-1,i++;
        while(s[i]>='0'&&s[i]<='9') x[p]=x[p]*10+s[i]-48,i++;
        if(semn==-1) x[p]=0-x[p];
        p++;
    }

    Max=INT_MIN;
    Front=1; Back=0;
    for(i=1; i<=n; ++i)
    {
        while(Front<=Back && x[i]<=x[Deque[Back]]) --Back;
        Deque[++Back]=i;
        if(Deque[Front]==i-k) ++Front;
        if(i>=k)
        {
            if(x[Deque[Front]]>Max)
            {
                start=i-k+1;
                stop=i;
                Max=x[Deque[Front]];
            }
        }
    }
    fout<<start<<" "<<stop<<" "<<Max<<"\n";
    return 0;
}