Cod sursa(job #2471665)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 11 octombrie 2019 10:38:06
Problema Secventa Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>

using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int aint[1000003][3],n,i,a,m,op,b,k,ma,in,sf;
void update(int st,int dr,int pos,int nod) {
	if(st==dr) {
		aint[nod][1]=a;
		aint[nod][2]=pos;
		while((aint[nod][1]<aint[nod/2][1] or aint[nod/2][2]==0) && nod>1) {
			swap(aint[nod],aint[nod/2]);
			nod/=2;
		}
	} else {
		int mij=(st+dr)/2;
		if(pos<=mij) {
			update(st,mij,pos,nod*2);
		} else {
			update(mij+1,dr,pos,nod*2+1);
		}
	}
}
void sterge(int nod) {
	aint[nod][1]=0;
	aint[nod][2]=0;
	if(nod<2*n) {
		if(aint[2*nod][1]<aint[2*nod+1][1] && aint[2*nod][2]!=0) {
			aint[nod][1]=aint[2*nod][1];
			aint[nod][2]=aint[2*nod][2];
			sterge(2*nod);
		} else if(aint[2*nod+1][2]!=0){
			aint[nod][1]=aint[2*nod+1][1];
			aint[nod][2]=aint[2*nod+1][2];
			sterge(2*nod+1);
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	f>>n>>k;
	for(i=1; i<=k; i++) {
		f>>a;
		update(1,n,i,1);
	}
	ma=-30001;
	if(aint[1][1]>ma) {
		ma=aint[1][1];
		in=1;
		sf=k;
	}
	for(i=k+1; i<=n; i++) {
		f>>a;
		update(1,n,i,1);
		while(aint[1][2]<=i-k) {
			sterge(1);
		}
		if(aint[1][1]>ma) {
			ma=aint[1][1];
			in=i-k+1;
			sf=i;
		}
	}
	g<<in<<" "<<sf<<" "<<ma<<'\n';
	return 0;
}