Cod sursa(job #171323)

Utilizator firewizardLucian Dobre firewizard Data 4 aprilie 2008 00:27:49
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>   
#include <stdlib.h>
#include <string.h>
struct blabla{int x;int y;};   
blabla deque[1000000];   
long max,s,n,k,p,capat,coada,a[1000000],i,P;   
char cit[3500014],*r;
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]);   */
    gets(cit);     
    r=cit;     
    for(i=1;i<n;++i)     
    {    
        a[i]=atol(r);     
        r=strchr(r,' ');     
        r++;     
    }     
    a[n]=atol(r);    

    
    capat=1;max=-150000000;   
    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);   
       
    return 0;   
}