Cod sursa(job #1202747)

Utilizator tudormaximTudor Maxim tudormaxim Data 29 iunie 2014 14:03:15
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<cstdio>
#include<cstring>
#include<iostream>
#define nmax 500009
#define inf 0x3f3f3f3f
using namespace std;
int n, k, vf, fin, sol=-inf, v[nmax],coada[nmax], x2;
char s[10*nmax];
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d %d",&n,&k);
    cin.get();
    cin.get(s,10*nmax);
    int i, semn = 0,l=strlen(s);
    ++l;
    s[l-1] = ' ';
    vf = 1;
    fin = 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 <= fin && v[i] <= v[coada[fin]])
            --fin;
        coada[++fin] = i;
        if(coada[vf] == i-k) vf++;
            if(v[coada[vf]] > sol && i >= k)
            {
                sol = v[coada[vf]];
                 x2 = i;
                }
    }
    cout<<x2-k+1<<" "<<x2<<" "<<sol;
    fclose(stdin);
    fclose(stdout);
    return 0;
}