Cod sursa(job #973057)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 13 iulie 2013 11:49:57
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<stdio.h>
#define Dim 500001
 
int q[Dim] ;
long ind[Dim] ;
 
 
int main()
{
 int x, max ;
 long poz, pr, ul, n, k, i, p, w, minus ;
 
 freopen("secventa.in","r",stdin) ;
 freopen("secventa.out","w",stdout) ;
 
 scanf("%ld %ld",&n,&k) ;
 
 // calculez minimul din primele k:
 pr = 0 ; ul = -1 ;
 scanf("%s", &sir);w=0;
 for (i=1; i<=k; i++)
  {
   //scanf("%d",&x);
   x=0;minus=0;
   if(sir[w]=='-')
    {
		minus=1;
		w++;
    }
   while(sir[w]>='0' && sir[w]<='9')
    {
		x=x*10+sir[w]-'0';
		w++;
    }
   if(minus==1)
	   x=-x;
   w++;
   while ((pr<=ul)&&(q[ul] >= x)) ul-- ;
   q[++ul] = x ;
   ind[ul] = i ;
  }
 max = q[pr] ;
 poz = 1 ;
 p = 1;
 // calculez restul:
 for ( ; i<=n; i++)
  {
   //scanf("%d",&x) ;
	x=0;minus=0;
   if(sir[w]=='-')
    {
		minus=1;
		w++;
    }
   while(sir[w]>='0' && sir[w]<='9')
    {
		x=x*10+sir[w]-'0';
		w++;
    }
   if(minus==1)
	   x=-x;
   w++;
   while ((q[ul] >= x) && (pr<=ul)) ul-- ;
   q[++ul] = x ;
   ind[ul] = i ;
   p++ ;
   if (ind[pr] <= i-k) pr++ ;
   if (max < q[pr]) { max = q[pr] ;poz = p; }
  }
 
 printf("%ld %ld %d\n",poz,poz+k-1,max) ;
 return 0 ;
}