Cod sursa(job #141329)

Utilizator yonutzTalos Ionut yonutz Data 22 februarie 2008 23:23:21
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<stdio.h>      
#include<string.h>      
#include<ctype.h>      
#define NMAX 500401      
char s[NMAX*8];      
int p,in,sf,x[NMAX],nr,i,j,semn,n,p1,p2,max,m,k,l,a,poz;      
struct deque      
{      
    int V,I;      
};      
deque q[NMAX];      
int main()      
{      
    freopen("secventa.in","r",stdin);      
    freopen("secventa.out","w",stdout);      
    scanf("%d%d",&n,&k);      
    gets(s);      
    gets(s);      
    poz=0;      
    m=strlen(s)-1;      
    n=0;      
    while (poz<=m)      
    {      
        if (s[poz]=='-')      
            semn=-1;      
        else     
        {      
            semn=1;      
            poz--;      
        }      
        nr=0;      
        while (isdigit(s[++poz]))      
            nr=nr*10+s[poz]-48;      
        poz++;      
        x[++n]=semn*nr;      
    }      
/*  for (i=1;i<=n;i++)    
        scanf("%d",&x[i]);*/     
    max=-35000;      
    in=1;      
    sf=1;      
    q[1].I=1;      
    q[1].V=x[1];      
    i=2;      
    for (i=2;i<=n;i++)      
    {      
    while (in<=sf&&q[in].I<=i-k)      
            in++;      
    while (sf>=in&&x[i]<=q[sf].V)      
        sf--;      
     
        q[++sf].V=x[i];      
        q[sf].I=i;      
        if (q[in].V>max&&i-k+1>0)      
        {      
            max=q[in].V;      
            p1=i-k+1;      
            p2=i;      
        }      
    }      
     
    printf("%d %d %d\n",p1,p2,max);      
     
    return 0;      
}