Cod sursa(job #2493)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 17 decembrie 2006 12:27:41
Problema SequenceQuery Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include<stdio.h>
#define fin "sequencequery.in"
#define fout "sequencequery.out"
#define NMAX 100001
#define SMAX 1000001
long n,m,min,max,val,a,b,segm[SMAX][3]; //segm: 0-min, 1-max
FILE *in,*out;

long maxf(long a,long b) {(a<b)?(a=b):(a); return a; }

void insert(long nod,long st,long dr) {
long m,x1,y1,x2,y2;
	if (a<=st && dr<=b) {
		segm[nod][0]=val;
		segm[nod][1]=val;
		segm[nod][2]=1;
	}
	else {
		m=(st+dr)/2;
		if (a<=m) insert(2*nod,st,m);
		else insert(2*nod+1,m+1,dr);
		
		if (!segm[2*nod][2]) { 
		       segm[nod][0]=segm[2*nod+1][0];
	       	       segm[nod][1]=segm[2*nod+1][1];
		       segm[nod][2]=segm[2*nod+1][2];
		}
		else
		if (!segm[2*nod+1][2]) {
			segm[nod][0]=segm[2*nod][0];
	       	       	segm[nod][1]=segm[2*nod][1];
			segm[nod][2]=segm[2*nod][2];
		}
		else {
			x1=segm[2*nod][0]; x2=segm[2*nod+1][0];
			y1=segm[2*nod][1]; y2=segm[2*nod+1][1];
			segm[nod][2]=1;
			if (x1<=x2) { 
				segm[nod][0]=x1;
				segm[nod][1]=maxf(y1,y2);
			}
			else {
				if (y1-x1>y2-x2) {
					segm[nod][0]=x1;
					segm[nod][1]=y1;
				}
				else {
					segm[nod][0]=x2;
					segm[nod][1]=y2;
				}
			}
		}
	}
}

void query(long nod,long st,long dr) {
long m,x1,y1,x2,y2;
	if (a<=st && dr<=b) {
		
		x1=min; x2=segm[nod][0];
		y1=max; y2=segm[nod][1];
		if (x1<=x2) { 
			min=x1;
			max=maxf(y1,y2);
			}
		else {
			if (y1-x1>y2-x2) {
				min=x1;
				max=y1;
				}
			else {
				min=x2;
				max=y2;
			}
		}
	}
	else {
		m=(st+dr)/2;
		if (a<=m) query(2*nod,st,m);
		if (b>m) query(2*nod+1,m+1,dr);
	}
}

int main() {
long i,k,s=0,tmp;
	in=fopen(fin,"r"); out=fopen(fout,"w");

	fscanf(in,"%ld%ld",&n,&m);
		
	val=0; a=0; insert(1,0,n);
	for (i=1;i<=n;i++) { 
		
		fscanf(in,"%ld",&k);
		
		s+=k; a=i; b=i;
		
		val=s;  
		
		insert(1,0,n);

	}
	
	for (i=1;i<=m;i++) {

		fscanf(in,"%ld%ld",&a,&b);
		
		--a;

		min=NMAX; max=-NMAX;	
		
		query(1,0,n);
		
		tmp=max-min;
		
		fprintf(out,"%ld\n",tmp);
	}
	
	fclose(in); fclose(out);

	return 0;
}