Cod sursa(job #196361)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 25 iunie 2008 21:28:57
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <stdio.h>   
#define N 500100   
#define min(a,b) a<b?a:b   
int n,k;   
int a[N],q[N],poz[N];   
int max=-(1<<30),pi,pf;   
char s[1<<22];   
void parsare(){   
    int i,j,x;   
    scanf("%d%d\n",&n,&k);   
    fgets(s,1<<22, stdin);   
    for(j=0,i=1;i<=n;++j,++i){   
        if(s[j]=='-'){   
            for(x=0,j++;s[j]>='0'&&s[j]<='9';++j)   
                x=x*10+(s[j]-48);   
            a[i]=x*(-1);   
        }   
        else{   
            for(x=0;s[j]>='0'&&s[j]<='9';++j)   
                x=x*10+(s[j]-48);   
            a[i]=x;   
        }   
    }   
}   
int main(void){   
    freopen("secventa.in", "r", stdin);   
    freopen("secventa.out", "w", stdout);   
    parsare();   
    int i,inc=1,sf=1,baza;   
    q[1]=a[1];   
    poz[1]=1;   
    for(i=2;i<k;++i){   
        while(a[i]<=q[sf]&&sf>0)   
            sf--;   
        q[++sf]=a[i];   
        poz[sf]=i;   
    }   
    for(i=k;i<=n;++i){   
        while(i-poz[inc]>=k)   
            ++inc;   
        baza=min(a[i],q[inc]);   
        if(baza>max){   
            max=baza;   
            pi=i-k+1;   
            pf=i;   
        }   
        while(a[i]<=q[sf]&&sf>0)   
            --sf;   
        q[++sf]=a[i];   
        poz[sf]=i;   
        if(inc>sf)   
            inc=sf;   
    }   
    printf("%d %d %d\n",pi,pf,max);   
    return 0;   
}