Cod sursa(job #250041)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 29 ianuarie 2009 21:44:57
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 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);
   char ca[lg_max*10],c;
   int j=0;
   int semn;
   scanf ("%c",&c);
   fgets(ca,lg_max,stdin);
   for (int i=1;i<=n;i++)
   {
       semn=0;
       sir[i]=0;
       while(ca[j]!='-' && (ca[j]<'0' || ca[j]>'9'))
            j++;
       if(ca[j]=='-')
         {
          semn=1;
          j++;
         }
       while(ca[j]>='0' && ca[j]<='9')
            {
             sir[i]=sir[i]*10+(ca[j]-'0');
             j++;
            }
       if(semn)
         sir[i]=-sir[i];
   }

     u=0;
     p=1;
     maxx=-2532634;
     for (int i=1;i<=n;i++)
     {
          while (u>=p && sir[i]<=sir[poz[u]])
               u--;
          poz[++u]=i;
          if (poz[p]==i-k)
               p++;
          if (i>=k)
          {
               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;
}