Cod sursa(job #141096)

Utilizator SycronVene Tian Sycron Data 22 februarie 2008 19:06:44
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 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;   
}