Cod sursa(job #198614)

Utilizator h_istvanHevele Istvan h_istvan Data 13 iulie 2008 02:20:26
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>  
#define MAXN 500000  
long n,k,b,e,max,maxh,i;  
long v[MAXN],s[MAXN];  
char sz[MAXN*10];
   
void add(long x)  
{  
     long i;  
     for(i=e;(i>=b) && (s[i]>x);--i);
     e=i+1;  
     s[e]=x;  
} 

void read()
{
     long i,j=0,s;
     scanf("%ld %ld\n",&n,&k);  
     gets(sz);
     for (i=1;i<=n;++i)
     {
         s=0;
         while((sz[j] != '-') && !((sz[j] >= '0') && (sz[j] <= '9'))) ++j;
         if(sz[j] == '-') s=1,++j;
         while((sz[j] >= '0') && (sz[j] <= '9')) v[i]=v[i]*10+(sz[j]-'0'),++j;
         if(s) v[i]*=-1;
     }
} 
  
int main()  
{  
    freopen("secventa.in","r",stdin);  
    freopen("secventa.out","w",stdout);  
       
    b=1;e=0;  
   
    read();
      
    for(i=1;i<=k;++i) add(v[i]);  
    max=s[b];maxh=1;  
     
    for (i=k+1;i<=n;++i)   
    {  
         if(v[i-k] == s[b]) b++;  
         add(v[i]);  
         if(s[b] > max) max=s[b],maxh=i-k+1;  
    }  
       
    printf("%ld %ld %ld\n",maxh,maxh+k-1,max);  
       
    return 0;  
}