Cod sursa(job #119927)

Utilizator alexeiIacob Radu alexei Data 3 ianuarie 2008 17:46:04
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 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);
    int i=1;
    char ok,semn='1';
     while(scanf("%c",&ok)!=EOF)
    {  
      
      if(ok!=' ')
       {if(ok!='-')
                   {
                      a[i]+=a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i];
                      a[i]+=int(ok)-48;}
                          else
                          semn='0';
      
       }
      else
      {
          if(semn=='0'){
          a[i]*=(-1);   
          semn='1';}     
      ++i;
      }   
    }
    co[u++]=1;
	for(i=2; i<=k; ++i){
        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(i=k+1; i<=n; ++i)
	{ 
      	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;
}