Cod sursa(job #250050)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 29 ianuarie 2009 22:26:00
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <stdio.h>
#define lg_max 500010

int sir[lg_max],poz[lg_max];
int n,k,u,p;
int maxx,pi;

int main ()
{
     freopen ("secventa.in","r",stdin);
     freopen ("secventa.out","w",stdout);
     scanf ("%d %d",&n,&k);
     for (int i=1;i<=n;i++)
          scanf ("%d",&sir[i]);

     u=0;
     p=1;
     maxx=-2532634;
    for (int i=1;i<=k;i++)
    {
          while (u>=p && sir[i]<=sir[poz[u]])
               u--;
          poz[++u]=i;
    }

     maxx=sir[poz[p]];
     pi=1;

     for (int i=k+1;i<=n;i++)
     {
          while (u>=p && sir[i]<=sir[poz[u]])
               u--;
          poz[++u]=i;
          if (poz[p]==i-k)
               p++;
          if (sir[poz[p]]>maxx)
          {
               maxx=sir[poz[p]];
               pi=i-k+1;
          }
     }

     printf("%d %d %d\n",pi,pi+k-1,maxx);
     return 0;
}