Cod sursa(job #2289817)

Utilizator DeleDelegeanu Alexandru Dele Data 25 noiembrie 2018 12:45:47
Problema Lupul Urias si Rau Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <iostream>
#include <fstream>
#define MAX 100001
std::ifstream f("lupu.in");
std::ofstream g("lupu.out");
struct oaie {
	int distance;
	int wool;
};
oaie v[MAX];
///Begin of quickSort
int partition(int left, int right) {
	int i = left;
	int j = right;
	oaie pivot = v[(left + right) / 2];

	while (i <= j) {
		while (v[i].distance < pivot.distance || (v[i].distance == pivot.distance && v[i].wool > pivot.wool))
			++i;
		while (v[j].distance > pivot.distance || (v[j].distance == pivot.distance && v[j].wool < pivot.wool))
			--j;
		if (i <= j) {
			std::swap(v[i], v[j]);
			++i;
			--j;
		}
	}

	return i;
}
void quickSort(int left, int right) {
	int index = partition(left, right);
	if (left < index - 1)
		quickSort(left, index - 1);
	if (index < right)
		quickSort(index, right);
}
///End of quickSort

class MaxHeap {
private:
	int size;
	oaie h[MAX];
	int father(int node) {
		return node / 2;
	}
	int leftSon(int node) {
		return node * 2;
	}
	int rightSon(int node) {
		return node * 2 + 1;
	}

	void sift(int k) {
		int son;
		do {
			son = 0;
			int lSon = leftSon(k);

			if (lSon <= size) {
				son = lSon;
			
				int rSon = rightSon(k);
				if (rSon <= size && h[rSon].wool > h[lSon].wool) {
					son = rSon;
				}

				if (h[son].wool <= h[k].wool) {
					son = 0;
				}
			}

			if (son) {
				std::swap(h[son], h[k]);
				k = son;
			}
		} while (son);
	}

	void percolate(int k) {
		oaie key = h[k];

		int kFather = father(k);
		while (k > 1 && key.wool > h[kFather].wool) {
			h[k] = h[kFather];
			k = kFather;
			kFather = father(k);
		}

		h[k] = key;
	}

public:
	MaxHeap(int size) {
		this->size = size;
	}

	int getMax() {
		return h[1].wool;
	}

	int getSize() {
		return this->size;
	}

	void insert(oaie value) {
		h[++size] = value;
		percolate(size);
	}

	void remove(int position) {
		h[position] = h[size];
		--size;

		if (position > 1 && h[position].wool > h[father(position)].wool)
			percolate(position);
		else
			sift(position);

	}
};



int main() {
	int n;
	f >> n;

	int x;
	f >> x;

	int l;
	f >> l;

	for (int i = 1; i <= n; ++i) {
		f >> v[i].distance >> v[i].wool;
	}

	quickSort(1, n);

	MaxHeap* h = new MaxHeap(0);

	int sol = 0;
	for (int dmax = x % l, i = 1; dmax <= x; dmax += l) {
	
		for (; v[i].distance <= dmax && i <= n; ++i) {
			h->insert(v[i]);
		}

		if (h->getSize()) {
			sol += h->getMax();
			h->remove(1);
		}

	}

	g << sol << '\n';

	return 0;
}