Cod sursa(job #186440)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 27 aprilie 2008 22:41:38
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
# include <stdio.h>
# include <string.h>

# define inf 500001
# define FIN "secventa.in"
# define FOUT "secventa.out"
# define MAX 3300000

long v[500001];
long deque[500001];
char s[MAX];

void parsare()
{
     int semn=1,ct=0,aux=0,lung,i;
     fgets(s,MAX,stdin);
     lung=strlen(s);
     for (i = 0; i <= lung; ++i)
       {
            if (s[i]=='-') semn=-1;
            if (s[i]>='0' && s[i]<='9')
              aux=aux*10+(s[i]-'0');
            if (s[i]==' ' || s[i]=='\n')
              {
                 if (semn==1) v[++ct]=aux;
                         else v[++ct]=-aux;
                 aux=0;
                 semn=1;
              }
       }
}

int main()
{
    long n,k,i;
    
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    
    scanf("%ld %ld\n", &n, &k);
    parsare();
      
    long start=1, stop=0;
    v[0]=-inf;
    
    for (i = 1; i <= k; i++)
      {
           while (v[deque[stop]]>v[i]) stop--;
           deque[++stop]=i;
      }
    
    long min=v[deque[start]], poz=k;
    
    for (i = k+1; i <= n; i++)
      {
           while (deque[start]<i-k+1) start++;
           while (v[deque[stop]]>v[i])
              if (stop!=start-1) stop--;
                            else break;
           deque[++stop]=i;
           if (v[deque[start]]>min)
             {
                 min=v[deque[start]];
                 poz=i;
             }
      }
    
    printf("%ld %ld %ld",poz-k+1,poz,min);
    
    return 0;
}