Cod sursa(job #496022)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 27 octombrie 2010 16:35:33
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
using namespace std;
#define DIM 100001

int N, X, Y, Z, L, V[DIM];
int Pm, Um, Dm[DIM];
int PM, UM, DM[DIM];
int Sw, Lmax, Poz;

void deque ()
{
	Sw = 0;
	Pm = PM = 1;
	Um = UM = 0; 
	for (int i = 1; i <= N; ++i)
	{
		while (Pm <= Um && V[i] <= V[Dm[Um]]) Um--;
		while (PM <= UM && V[i] >= V[DM[UM]]) UM--;
		
		Dm[++Um] = i;
		DM[++UM] = i;
		
		if (i - L >= Dm[Pm]) Pm++;
		if (i - L >= DM[PM]) PM++;
		
		if (i >= L && V[DM[PM]] - V[Dm[Pm]] <= Z)
		{
			Sw = 1;
			if (Lmax < L)
				Lmax = L, Poz = i;
			else if (Lmax == L && Poz < i)
				Poz = i;			
		}	
	}
}

void cit ()
{
	ifstream f ("sir.in");
	f >> N >> X >> Y >> Z;
	for (int i = 1; i <= N; ++i)
		f >> V[i];
	f.close ();
	
	Lmax = -1;
}

void bin ()
{
	while (X <= Y)
	{
		L = (X + Y) / 2;
		deque ();
		if (Sw)
			X = L + 1;
		else
			Y = L - 1;
	}	
}

void afs ()
{
	ofstream f ("sir.out");
	f << Lmax;
	if (Lmax != -1)
		f << ' ' << Poz - Lmax + 1 << ' ' << Poz; 
	f.close ();
}

int main ()
{
	cit ();
	bin ();
	afs ();
}