Cod sursa(job #1414604)

Utilizator popescu.octavianPopescu Octavian popescu.octavian Data 2 aprilie 2015 19:55:00
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <cstdio>
#define nmax 500001

using namespace std;

int n, a[nmax], dq[nmax], i, p, u, first, last, Max, k, j, semn, x;
char s[nmax+1];

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d %d\n",&n,&k);
    fgets(s,nmax,stdin);
    for(i=1;i<=n;i++)
    {
        if(s[j]=='-')
            semn=-1, j++;
        else semn=1;
        x=0;
        while(s[j]>='0'&&s[j]<='9')
        {
            x=x*10+s[j]-'0';
            j++;
        }
        j++;
        a[i]=semn*x;
    }
    p=1; u=0;
    for(i=1;i<=n;i++)
    {
        if(p<=u&&a[i]<=a[dq[u]]) u--;
        dq[++u]=i;
        if(dq[p]==i-k) p++;
        if(i>=k&&a[dq[p]]>=Max) Max=a[dq[p]], first=i-k+1, last=i;
    }
    printf("%d %d %d",first,last,Max);
    return 0;
}