Cod sursa(job #35784)

Utilizator lucibitLucian Onea lucibit Data 22 martie 2007 15:27:52
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 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;
 }
void citire()
{long int i;
 FILE *f=fopen("secventa.in","r");
 fscanf(f,"%ld %ld\n",&n,&k);
 for(i=1;i<=n;i++) {fscanf(f,"%d ",&A[i]);
                    if(i<=k) insert(A[i],i);}
 fclose(f);
 }

int query()
{while (poz-deque[cap][1]>=k && cap<=coada) {cap++; }
 P=deque[cap][1];
 return deque[cap][0];
 }
int main ()
{cap=1;
 citire();
 long int i;
 long int pi,pf;
 int m;
 Max=deque[cap][0]; pi=1;pf=k;P=deque[cap][1];
 for(i=k+1,poz=k+1;i<=n;i++,poz++)
 {insert(A[i],i);
	m=query();
	if(Max<m) {Max=m;pi=P; pf=poz;}


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