Cod sursa(job #35788)

Utilizator lucibitLucian Onea lucibit Data 22 martie 2007 15:32:42
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<stdio.h>
#define MaxN 500001
long int n,k,Max;
int deque[MaxN][2],cap,coada,P,A[MaxN],poz;
void insert(long int v, long int p)
{while (cap<=coada && v<deque[coada][0]) coada--;
  coada++; deque[coada][0]=v;
  deque[coada][1]=p;
 }


int query()
{while (poz-deque[cap][1]>=k && cap<=coada) {cap++; P++; }

 return deque[cap][0];
 }
int main ()
{cap=1;

 long int i;
 long int pi,pf;
 int m;
 FILE *f=fopen("secventa.in","r");
 fscanf(f,"%ld %ld\n",&n,&k);
 for(i=1;i<=k;i++) {fscanf(f,"%d ",&A[i]); insert(A[i],i);}

 Max=deque[cap][0]; pi=1;pf=k;P=deque[cap][1];
 for(i=k+1,poz=k+1;i<=n;i++,poz++)
 { fscanf(f,"%d ",&A[i]);
  insert(A[i],i);
	m=query();
	if(Max<m) {Max=m;pi=P; pf=poz;}
	 P=deque[cap][1];

	}
fclose(f);
FILE *g=fopen("secventa.out","w");
fprintf(g,"%ld %ld %ld",pi,pf,Max);
fclose(g);
return 0; }