Cod sursa(job #43835)

Utilizator FlorianFlorian Marcu Florian Data 30 martie 2007 16:17:28
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include<stdio.h>
#include<values.h>
int main()
{long a[500001],q[500001],rez,n,k,i,st,dr,poz;
FILE*f=fopen("secventa.in","r");
FILE*g=fopen("secventa.out","w");
fscanf(f,"%ld %ld",&n,&k);
for (i=1;i<=n;i++) fscanf(f,"%ld",&a[i]);
rez=-MAXINT;
st=1;dr=0;
for (i=1;i<k;i++)
 {
 while(dr>=st&&a[i]<=a[q[dr]]) dr--;
 dr++;
 q[dr]=i;}
for (i=k;i<=n;i++)
	{
	while(st<=dr&&a[i]<=a[q[dr]]) dr--;
	dr++;
	q[dr]=i;
	while(st<=dr&&q[st]<i-k+1) st++;
	if (a[q[st]]>rez) {rez=a[q[st]]; poz=i;}}
fprintf(g,"%ld %ld %ld",poz-k+1,poz,rez);
fclose(f);
fclose(g);
return 0;}