Cod sursa(job #119902)

Utilizator alexeiIacob Radu alexei Data 3 ianuarie 2008 17:00:27
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<stdio.h>
int n,k,a[500001],co[500001],min,minmax;
int cauta(int p,int u,int x)
{
	int m;
	while(p<u){
		m=(p+u)/2;
		if(x<=a[co[m]])
			u=m;
		else
			p=m+1;
	}
	if(a[co[p]]<x)
		return p+1;
	return p;
}

int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	int min=30001,max,p=0,u=0,aa,bb;
	scanf("%d%d\n",&n,&k);
	char ok,semn='1';
	 while(scanf("%c",&ok)!=EOF)
	 { 
   if(ok==' ')
        break;
      if(ok!='-'){
       a[1]*=10;
	   a[1]+=int(ok)-48;}
     else
       semn='0';
     }
     if(semn=='0')
     a[1]*=(-1);
    co[u++]=1;
	for(int i=2; i<=k; i++){
		semn='1';
        while(scanf("%c",&ok)!=EOF)
     {
   if(ok==' ')  
        break;
      if(ok!='-'){
       a[i]*=10;
	   a[i]+=int(ok)-48;}
     else
       semn='0';
     }
      if(semn=='0')
      a[i]*=(-1);
        u=cauta(p,u-1,a[i]);
		co[u++]=i;
		if(a[co[p]]<min)
			min=a[co[p]];
	}
	max=min;
	aa=1;bb=k;
	for(int i=k+1; i<=n; i++)
	{semn='1';
  while(scanf("%c",&ok)!=EOF)
     {                
   if(ok==' ')  
        break;  
      if(ok!='-'){
       a[i]*=10;
	   a[i]+=int(ok)-48;}
     else
       semn='0';
     }
      if(semn=='0')
      a[i]*=(-1);
      
      	if(co[p]+k<=i)
			++p;
		u=cauta(p,u-1,a[i]);
		co[u++]=i;
		min=a[co[p]];
		if(min>max){
			max=min;
			aa=i-k+1;
			bb=i;
		}
	} 
    printf("%d %d %d\n",aa,bb,max);
	return 0;
}