Pagini recente » Cod sursa (job #468) | Cod sursa (job #2460678) | Cod sursa (job #2583654) | Cod sursa (job #1232909) | Cod sursa (job #496022)
Cod sursa(job #496022)
#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 ();
}