Cod sursa(job #327990)

Utilizator radu_cppRadu Voroneanu radu_cpp Data 30 iunie 2009 18:23:53
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <string.h>
#define FIN "secventa.in"
#define FOUT "secventa.out"

long p, x, n, k, i=0, st, dr, rez, poz=0, a[500000], q[500000], lung;
char s[3500000];
int main()
  {
        freopen(FIN, "r", stdin);
        freopen(FOUT, "w", stdout);
        scanf("%ld %ld\n", &n, &k);
        fgets(s,3500000,stdin);
	lung=strlen(s)-1;
	while (i<lung) 
	{
		p=1; x=0;
		if (s[i]=='-')
		{
			p=-1;
			++i;
		}
		for ( ; (s[i]!=' ')&&(i<lung); ++i)
                 { x=x*10+s[i]-48; }
		++poz;
		a[poz]=x*p;
		++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;
   }