Cod sursa(job #2529249)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 23 ianuarie 2020 09:48:10
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.52 kb
#include<fstream>

using namespace std;
int n,k,i,mi[500001],v[500001],ma,p,u,st,dr;
FILE *f;
ofstream g("secventa.out");
int main()
{
	f = fopen("secventa.in","r");
	fscanf(f,"%d%d",&n,&k);
	ma = -30001;
	for(i = 1;i <= n; ++i)
		fscanf(f,"%d",&v[i]);
	p = u = 1;
	mi[p] = 1;
	for(i = 2; i <= n; ++i)
	{
		while(p <= u && v[i] <= v[mi[u]])
			u--;
		u++;
		mi[u] = i;
		while(p <= u && i - mi[p] >= k)
			p++;
		if(v[mi[p]] > ma && i >= k)
		{
			ma = v[mi[p]];
			dr = i;
		}
	}
	g << dr - k + 1 << " " << dr << " " << ma;
	return 0;
}