Cod sursa(job #1414088)

Utilizator theprdvtheprdv theprdv Data 2 aprilie 2015 12:39:37
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

fstream fin("lupu.in", ios::in);
fstream fout("lupu.out", ios::out);

#define MAXN 100005
#define father(x) x / 2
#define l_son(x) x * 2
#define r_son(x) x * 2 + 1
int N, X, L, maxx;
unsigned long long int sol;
vector <long long int> sheeps[MAXN];
int heap[MAXN];

void read()
{
	fin >> N >> X >> L;
	for (int i = 1, w, z, gr; i <= N; i++){
		fin >> w >> z;
		if (w > X) continue;
		if(w > 0) gr = (w - 1) / L + 1;
		else gr = 0;
		if (gr > maxx) maxx = gr;
		sheeps[gr].push_back(z);
	}
	fin.close();
}
void percolate(int k)
{
	while (k > 1 && heap[father(k)] < heap[k])
		swap(heap[k], heap[father(k)]),
		k = father(k);
}
void cut()
{
	heap[1] = heap[heap[0]--];
	int son, k = 1;
	do{
		son = l_son(k);
		if (heap[r_son(k)] > heap[son]) son = r_son(k);
		if (son > heap[0] || heap[son] < heap[k]) son = 0;
		if (son)
			swap(heap[k], heap[son]),
			k = son;
	} while (son);
}

int main() 
{
	read();
	for (int i = 0; i <= maxx; i++){
		while (!sheeps[i].empty()){
			//heap.push(sheeps[i].back());
			heap[++heap[0]] = sheeps[i].back();
			percolate(heap[0]);
			sheeps[i].pop_back();
		}
		int add = 0;
		//if (heap.size())  add = heap.top(), heap.pop();
		if (heap[0]) add = heap[1], cut();
		sol += add;
	}
	fout << sol << "\n";
	
	fout.close();
	return 0;
}