Cod sursa(job #2254719)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 5 octombrie 2018 20:43:28
Problema Distincte Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <bits/stdc++.h>
using namespace std;

FILE *f1 = fopen("secvdist.in", "r");
FILE *f2 = fopen("secvdist.out", "w");

const int kPInf = 1000000001;
const int kMInf = -1000000001;
const int kMax = 2100000;

int arbmax[kMax], arbmin[kMax], v[kMax / 4 + 5];

void updateMax(int node, int left, int right, int poz, int val) {
	if (left == right) {
		arbmax[node] = val;
		return;
	}

	int mij = left + (right - left) / 2;
	if (poz <= mij)
		updateMax(2 * node, left, mij, poz, val);
	else
		updateMax(2 * node + 1, mij + 1, right, poz, val);

	arbmax[node] = max(arbmax[2 * node], arbmax[2 * node + 1]);
}

void updateMin(int node, int left, int right, int poz, int val) {
	if (left == right) {
		arbmin[node] = val;
		return;
	}

	int mij = left + (right - left) / 2;
	if (poz <= mij)
		updateMin(2 * node, left, mij, poz, val);
	else
		updateMin(2 * node + 1, mij + 1, right, poz, val);

	arbmin[node] = min(arbmin[2 * node], arbmin[2 * node + 1]);
}

int queryMax(int node, int left, int right, int sL, int sR) {
	if (sL <= left && right <= sR)
		return arbmax[node];

	int mij = left + (right - left) / 2, maxs1, maxs2;
	if (sL <= mij)
		maxs1 = queryMax(2 * node, left, mij, sL, sR);
	else maxs1 = kMInf;

	if (mij < sR)
		maxs2 = queryMax(2 * node + 1, mij + 1, right, sL, sR);
	else
		maxs2 = kMInf;

	return max(maxs1, maxs2);
}

int queryMin(int node, int left, int right, int sL, int sR) {
	if (sL <= left && right <= sR)
		return arbmin[node];
	int mij = left + (right - left) / 2;
	int mins1, mins2;
	if (sL <= mij)
		mins1 = queryMin(2 * node, left, mij, sL, sR);
	else mins1 = kPInf;

	if (mij < sR)
		mins2 = queryMin(2 * node + 1, mij + 1, right, sL, sR);
	else
		mins2 = kPInf;

	return min(mins1, mins2);
}


int main () {

	int n, k;

	for (int i = 0; i < kMax; i++) {
		arbmax[i] = kMInf;
		arbmin[i] = kPInf;
	}

	fscanf(f1, "%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		fscanf(f1, "%d", &v[i]);
		updateMax(1, 1, n, i, v[i]);
		updateMin(1, 1, n, i, v[i]);
	}

	fclose(f1);

	int maxs, mins, sw = 0, i, j, mij, sol = -1;
	i = 1, j = n;
	while (i <= j) {
		mij = i + (j - i) / 2;

		sw = 0;
		for (int p = 1; p <= n; p++) {
			if (p + mij - 1 > n)
				break;
			maxs = kMInf;
			mins = kPInf;
			maxs = queryMax(1, 1, n, p, p + mij - 1);
			mins = queryMin(1, 1, n, p, p + mij - 1);

			if (maxs - mins <= k) {
				sw = 1;
				break;
			}
		}

		if (sw == 1) {
			sol = mij;
			i = mij + 1;
		}
		else
			j = mij - 1;

	}
	fprintf(f2, "%d\n", sol);
	fclose(f2);
	return 0;
}