Cod sursa(job #1223823)

Utilizator Narcis_NeculaNecula Narcis Narcis_Necula Data 28 august 2014 22:23:29
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <cstdio>
using namespace std;
int n,k,a[500005],lista[500005][2],st,dr,inceput,sfirsit,baza;
char c;
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d %d\n",&n,&k);
    c=' ';
    int i=0,semn=1;
    while (c!=EOF && c!='\n')
     {
         if (c==' ')
         a[i]*=semn,semn=1,++i;
         else
         {
             if (c=='-')
             semn=-1;
             else
             {
                 a[i]=a[i]*10+(int)(c-'0');
                 }
                  }
                   c=getchar();
                   }
                   a[n]*=semn;
                    st=1; dr=1;
                    lista[1][0]=40000;
                     lista[1][1]=0;
                     for (int i=1;i<=k;++i)
                      {
                          ++dr;
                          while (dr>st && lista[dr-1][0]>a[i]) --dr;
                          lista[dr][0]=a[i];
                          lista[dr][1]=i;
                          }
                          baza=lista[st][0];
                          inceput=1;
                          sfirsit=k;
                          for (int i=k+1;i<=n;++i)
                           {
                               if (i-lista[st][1]==k)
                               ++st;
                               ++dr;
                               while (dr>st && lista[dr-1][0]>a[i])
                               --dr;
                               lista[dr][0]=a[i];
                               lista[dr][1]=i;
                               if (lista[st][0]>baza)
                               {
                                   baza=lista[st][0];
                                   inceput=i-k+1;
                                   sfirsit=i;
                                   }
                                   }
                                   printf("%d %d %d",inceput,sfirsit,baza);
                                   fclose(stdin);
                                   fclose(stdout);
                                   return 0;
                                   }