Cod sursa(job #822463)

Utilizator razyelxrazyelx razyelx Data 23 noiembrie 2012 17:01:21
Problema Heapuri Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.81 kb
#include <vector>
#include <fstream>

using namespace std;

class Heap
{
private:
	vector<long long> storage;
	vector<long long> positions;
	vector<long long> timestamps;
public:
	Heap()
	{
		//starting from 1;
		storage.push_back(-1);
		positions.push_back(-1);
		timestamps.push_back(-1);
	}
	void push(long long value) 
	{
		storage.push_back(value);
		positions.push_back(positions.size());
		timestamps.push_back(timestamps.size());
		int position = storage.size()-1;
		for (;position > 1;) 
		{
			if (storage.at(position) < storage.at(position / 2))
			{
				int temp = storage.at(position);
				storage.at(position) = storage.at(position / 2);
				storage.at(position / 2) = temp;
				
				temp = positions.at(position);
				positions.at(position) = positions.at(position / 2);
				positions.at(position / 2) = temp;
				
				temp = timestamps.at(positions[position]);
				timestamps.at(positions[position]) = timestamps.at(positions[position / 2]);
				timestamps.at(positions[position / 2]) = temp;
				
				position /= 2;
			} 
			else
			{
				break;	
			}				
		}		
	}
	
	long long pop(int index = 1)
	{
		long long lastValue = storage.at(storage.size()-1);
		int position = index;
		int min = storage.size()-1;
		int top = storage[position];
		storage[position] = lastValue;
		int temp = positions.at(position);
		positions.at(position) = positions.at(min);
		positions.at(min) = temp;
			
		temp = timestamps.at(positions[position]);
		timestamps.at(positions[position]) = timestamps.at(positions[min]);
		timestamps.at(positions[min]) = temp;
		for (;;)
		{
			int i = position*2;
			int j = position*2+1;
			if (i > storage.size()-1 || j > storage.size()-1)
			{
				break;
			}
			if (storage.at(i) < storage.at(j))
			{
				min = i;
			}
			else
			{
				min = j;
			}			
			
			temp = storage[position];
			storage[position] = storage[min];
			storage[min] = temp;
			
			temp = positions.at(position);
			positions.at(position) = positions.at(min);
			positions.at(min) = temp;
			
			temp = timestamps.at(positions[position]);
			timestamps.at(positions[position]) = timestamps.at(positions[min]);
			timestamps.at(positions[min]) = temp;
			
			position = min;
		}
		storage.pop_back();
		return top;
	}
	
	long long top()
	{
		return storage.at(1);
	}
	
	int getIndexByTimestamp(int timestamp)
	{
		return timestamps[timestamp];
	}	
	
};

int main(){	
	ifstream fin("heapuri.in");
	ofstream fout("heapuri.out");
	int n;
	Heap heap;
	fin >> n;	
	for (int i = 0; i < n; i++)
	{
		int x = 0;
		fin >> x;
		switch (x)
		{
		case 1:
			fin >> x;
			heap.push(x);
			break;
		case 2:
			fin >> x;
			heap.pop(heap.getIndexByTimestamp(x));
			break;
		case 3:
			fout << heap.top() << "\n";
			break;
		}
	}	
	return 0;
	
}