Cod sursa(job #119918)

Utilizator alexeiIacob Radu alexei Data 3 ianuarie 2008 17:26:35
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<stdio.h>
#include<iostream>
using namespace std;
int n,k,a[500001],co[500001],min,minmax;
char au[1000002];
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 r,t=1;
    int i;
     while(scanf("%c",&au[t])!=EOF)
     ++t;    
     --t; 
    char semn='1';
    for(r=1; au[r]!=' '; ++r)
   { 
     if(au[r]!='-'){
      a[1]+=a[1]+a[1]+a[1]+a[1]+a[1]+a[1]+a[1]+a[1]+a[1];
      a[1]+=int(au[r])-48;}
     else
      semn='0';
   }
    if(semn=='0') 
    a[1]*=-1;
    char ok;
    co[u++]=1;
	for(i=2; i<=k; i++){
		semn='1';++r;
       for(r; r<t&&au[r]!=' '; ++r)
     {  
       if(au[i]!='-'){
       a[i]+=a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i];
       a[i]+=int(au[r])-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(i=k+1; i<=n; i++)
	{	semn='1';  ++r;     
       for(r; r<t&&au[r]!=' '; ++r)
     { 
       if(au[i]!='-'){
       a[i]+=a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i]+a[i];
       a[i]+=int(au[r])-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;
}