Cod sursa(job #79664)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 23 august 2007 14:33:46
Problema SequenceQuery Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<stdio.h>
#include<string.h>


long long a[100005], n, m, x, y, nr;

void suma(int p, int u)
{
  long long sc, max, i;
  sc=max=a[p];
  for (i=p+1; i<=u; i++)
    {
      if (sc<0) sc=a[i];
	else sc+=a[i];
      if (sc>max) max=sc;
    }
  printf("%lld\n",max);
}

int main()
{
  long long i;
  freopen ("sequencequery.in","r",stdin);
  freopen ("sequencequery.out","w",stdout);
  scanf ("%lld %lld",&n, &m);

  long semn=0, aux;
  char sir[2500024];
  fgetc(stdin);
  fgets(sir, 2500024,stdin);
  aux=strlen(sir);
  nr=1;
  for (i=0; i<aux; i++)
    {
      if (sir[i]=='-') semn=1;
      if (sir[i]>='0' && sir[i]<='9')
	{	
	  a[nr]=a[nr]*10+sir[i]-'0';
	}
      if (sir[i]==' ' && semn)	a[nr]*=-1, semn=0;
      if (sir[i]==' ') nr++;
    }

  for (i=1; i<=m; i++)
    {
      scanf("%lld %lld",&x, &y);
      suma(x,y);
    }
  return 0;
}