Cod sursa(job #347231)

Utilizator chera_laryCHERA Laurentiu chera_lary Data 11 septembrie 2009 15:55:46
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#define fin "secventa.in"
#define fout "secventa.out"
#define nMax 500001
#define Inf 30001

using namespace std;

int n,k,poz,pozs,maximum=-Inf;
int s[nMax], mheap[nMax], c[nMax];

void citeste(){
	fstream in(fin, ios::in);
	in>>n>>k;
	for(int i=1;i<=n;i++)
		in>>s[i];
	in.close();
}

void combina(int i, int len){
	int tata, fiu, aux;
	tata=i; fiu=2*i;
	while(fiu<=len){
		if(fiu+1<=len)
			fiu=(mheap[fiu]<mheap[fiu+1])?fiu:fiu+1;
		if(mheap[tata]>mheap[fiu]){
			aux=mheap[tata];
			mheap[tata]=mheap[fiu];
			mheap[fiu]=aux;
			tata=fiu; fiu*=2;
		}else break;
	}
}

void do_heap(){
	for(int i=1;i<=k;i++)
		mheap[i]=s[i];
	combina(1,k);
	c[1]=mheap[1];
	maximum=c[1], poz=1;
}

void Secventa(){
	do_heap();
	for(int i=2;i<=n-k+1;i++){
		for(int j=1;j<=k;j++)
			if(mheap[j]==s[i-1])
				mheap[j]=s[i];
		combina(1,k);
		c[i]=mheap[1];
		if(maximum<c[i])
			maximum=c[i],poz=i;
	}
	pozs=poz+k;
	while(s[pozs]>=maximum&&pozs<=n) pozs++;
}

void tipar(){
	fstream out(fout,ios::out);
	out<<poz<<" "<<--pozs<<" "<<maximum<<endl;
	out.close();
}

int main(void){
	citeste();
	Secventa();
	tipar();
	return 0;
}