Cod sursa(job #57614)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 2 mai 2007 18:06:38
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#define FIN "secventa.in"
#define FOUT "secventa.out"

long int n, k, i, st, dr, rez, poz;
long int a[500000],q[500000];

int main()
  {
        freopen(FIN, "r", stdin);
        freopen(FOUT, "w", stdout);

        scanf("%ld %ld\n", &n, &k);
        for (i=1; i<=n; i=i+1)
         scanf("%ld ", &a[i]);
        rez=-2000000000;
        st=1;
        dr=0;
        for (i=1; i<k; i=i+1)
         {

          while ((dr>=st) and (a[i]<=a[q[dr]]))
           {
           dr=dr-1;
           }
          dr=dr+1;
          q[dr]=i;

          }
        for (i=k; i<=n; i=i+1)
         {

          while ((dr>=st) and (a[i]<=a[q[dr]]))
           {
           dr=dr-1;
           }
          dr=dr+1;
          q[dr]=i;
          while ((st<=dr) and (q[st]<i-k+1))
           {
           st=st+1;
           }
          if (a[q[st]]>rez)
           {
            rez=a[q[st]];
            poz=i;
           }
           
         }
        printf("%ld %ld %ld\n", poz-k+1, poz, rez);
        fclose(stdin); fclose(stdout);
        return 0;
   }