Cod sursa(job #1202751)

Utilizator tudormaximTudor Maxim tudormaxim Data 29 iunie 2014 14:10:00
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<fstream>
#include<cstring>
#define nmax 500009
using namespace std;
int n,k,sol = -40000,v[nmax],coada[nmax],vf,sf,x2;
char s[10*nmax];
int main()
{
    ifstream in("secventa.in");
    ofstream out("secventa.out");
    in>>n>>k;
    in.get();
    in.get(s,10*nmax);
    int i,semn = 0,l = strlen(s);
    ++l;
    s[l-1] = ' ';
    vf = 1;
    sf = 0;
    int nr = 0,d = 0;
    for(i = 0 ; i < l ; i++)
    {
        if(s[i]<='9' && s[i] >='0') nr= nr*10+s[i]-'0';
        if(s[i] == '-') semn = 1;
        if(s[i] == ' '){
            v[++d] = nr;
            if(semn == 1)
                v[d] = -v[d];
            semn = nr = 0;
        }
    }
    for(i = 1 ; i <= n ; i++)
    {
        while(vf <= sf && v[i] <= v[coada[sf]])
            --sf;
        coada[++sf] = i;
        if(coada[vf] == i-k) vf++;
            if(v[coada[vf]] > sol && i >= k)
            {
                sol = v[coada[vf]];
                 x2 = i;
            }

    }
    out<<x2-k+1<<" "<<x2<<" "<<sol;
    return 0;
}