Cod sursa(job #66994)

Utilizator nuexistnuexist nuexist Data 22 iunie 2007 00:50:48
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>
#define oo 0x3f3f3f3f
FILE *f=fopen("secventa.in","r"), *g=fopen("secventa.out","w");
int n,i,a[500001],coada[500001][2],prim,ultim,max,k,S,P,r;

void insert(int value, int pos)
{
	while(prim<=ultim && value<coada[ultim][0]) --ultim;
	coada[++ultim][0]=value;
	coada[ultim][1]=pos;
}

int query()
{
	while(prim<=ultim && coada[prim][1]<P) ++prim;
	return coada[prim][0];
}

int main()
{
	fscanf(f,"%d %d",&n,&k);
	for(i=1;i<=n;i++) fscanf(f,"%d",&a[i]);
	fclose(f);
	
	prim=1;ultim=0;S=0;max=-oo;
	for(i=1 ; i<k ; i++)  insert(a[i], i);
	
	for(i=k , P=1 ; i<=n ; ++i , ++P )
    {
	  insert(a[i], i);
	  r=query();
      if(r>max) max=r, S=i;
    }
	
	int poz=S-k+1;
	
	fprintf(g,"%d %d %d\n", poz, S, max);

	fclose(g);
	return 0;
}