Cod sursa(job #170917)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 3 aprilie 2008 14:54:32
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <stdio.h>
#define inf 1000000000

struct blabla{int x;int y;};   
blabla deque[500005];   
long max,s,n,k,p,capat,coada,a[500005],i,P;

void in(long v,long p)   
{
   while(capat<=coada&&v<deque[coada].x)--coada;   
   ++coada;deque[coada].x=v;deque[coada].y=p;   
}
   
int query(){   
     while(capat<=coada&&deque[capat].y<P)++capat;   
     return deque[capat].x;   
}
   
int main(){   
    freopen("secventa.in","r",stdin);   
    freopen("secventa.out","w",stdout);   
    
    scanf("%ld %ld\n",&n,&k);
    for (i=1;i<=n;++i)   
        scanf("%ld ",&a[i]);
    fclose(stdin);
    
    capat=1;max=-inf;
    
    for(i=1;i<k;++i)in(a[i],i);
    for(i=k,P=1;i<=n;++i,++P){   
       in(a[i],i);
       if(query()>max){max=query();s=i;}
    }
    printf("%ld %ld %ld",s-k+1,s,max);   
fclose(stdout);

return 0;   
}