Cod sursa(job #198609)

Utilizator h_istvanHevele Istvan h_istvan Data 13 iulie 2008 01:53:09
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <stdio.h>
#define MAXN 500000
long n,k,b,e,max,maxh,i;
long v[MAXN],s[MAXN];

void add(long x)
{
     long i;
     for(i=e;(i>=b) && (s[i] > x);--i);
     e=i+1;
     s[e]=x;
}

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    
    b=1;e=0;
    
    scanf("%ld %ld\n",&n,&k);
    for(i=1;i<=n;++i) scanf("%ld ",&v[i]);
    
    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;
}