#include <iostream>
#include <vector>

#include "dzialka.h"
#include "message.h"

#define COLLECTING_NODE 50
#define NODES_COUNT 100
#define MAX_FIELD_SIZE 75000

#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define MAX(x, y) ((x) > (y) ? (x) : (y))

typedef std::pair<int, int> tileRange;

/*inline bool isInRange(tileRange range, int value)
{
	return (value >= range.first && value < range.second);
}

inline bool rangesOverlapped(tileRange range0, tileRange range1)
{
	if (isInRange(range0, range1.first) || isInRange(range0, range1.second) || isInRange(range1, range0.first) || isInRange(range1, range0.second))
	{
		return true;
	}

	return false;
}*/

inline tileRange getRangesOverlap(tileRange range0, tileRange range1)
{
	return tileRange(MAX(range0.first, range1.first), MIN(range0.second, range1.second));
}

inline long long countSubrangesInRanges(std::vector<tileRange> &ranges)
{
	long long count = 0;

	for (tileRange range : ranges)
	{
		int rangeSize = range.second - range.first;
		count += (rangeSize * (rangeSize + 1)) / 2;
	}

	return count;
}

// TODO: don't copy these damn vectors
inline std::vector<tileRange> *applyRangesOverlap(std::vector<tileRange> &ranges0, std::vector<tileRange> &ranges1)
{
	std::vector<tileRange> *rangesOverlap = new std::vector<tileRange>();
	rangesOverlap->reserve(ranges0.size() + ranges1.size());

	int currentRange0Index = 0;
	int currentRange1Index = 0;

	while (currentRange0Index < ranges0.size() && currentRange1Index < ranges1.size())
	{
		tileRange overlap = getRangesOverlap(ranges0[currentRange0Index], ranges1[currentRange1Index]);

		if (overlap.first < overlap.second) // non-zero range
		{
			rangesOverlap->push_back(overlap);
		}
		
		if (ranges0[currentRange0Index] < ranges1[currentRange1Index])
		{
			currentRange0Index++;
		}
		else
		{
			currentRange1Index++;
		}
	}

	return rangesOverlap;
}

void workerRowsRectangles(int currentNode)
{
	int fieldWidth = GetFieldWidth();
	int fieldHeight = GetFieldHeight();

	/* Count rectangles */
	long long rectanglesCount = 0;

	for (int startingRowIndex = currentNode - (NODES_COUNT / 2); startingRowIndex < fieldHeight; startingRowIndex += (NODES_COUNT / 2))
	{
		int senderNode = startingRowIndex % (NODES_COUNT / 2);
		PutInt(senderNode, startingRowIndex / (NODES_COUNT / 2));
		Send(senderNode);
		Receive(senderNode);

		int rangesCount = GetInt(senderNode);

		std::vector<tileRange> currentRowRanges;
		currentRowRanges.reserve(rangesCount);

		for (int i = 0; i < rangesCount; i++)
		{
			currentRowRanges.push_back(std::pair<int, int>(GetInt(senderNode), GetInt(senderNode)));
		}



		rectanglesCount += countSubrangesInRanges(currentRowRanges);

		for (int rowIndex = startingRowIndex + 1; rowIndex < fieldHeight; rowIndex++)
		{
			int senderNode = rowIndex % (NODES_COUNT / 2);
			PutInt(senderNode, rowIndex / (NODES_COUNT / 2));
			Send(senderNode);
			Receive(senderNode);

			int rangesCount = GetInt(senderNode);

			std::vector<tileRange> nextRowRanges;
			nextRowRanges.reserve(rangesCount);

			for (int i = 0; i < rangesCount; i++)
			{
				nextRowRanges.push_back(std::pair<int, int>(GetInt(senderNode), GetInt(senderNode)));
			}

			currentRowRanges = *applyRangesOverlap(currentRowRanges, nextRowRanges);

			if (currentRowRanges.size() == 0)
			{
				break;
			}

			rectanglesCount += countSubrangesInRanges(currentRowRanges);
		}
	}

	PutLL(COLLECTING_NODE, rectanglesCount);
	Send(COLLECTING_NODE);
}

void workerRowsRanges(int currentNode)
{
	int fieldWidth = GetFieldWidth();
	int fieldHeight = GetFieldHeight();

	/* Calculate ranges per row */
	std::vector<std::vector<tileRange>> rowsRanges;
	rowsRanges.reserve(fieldHeight / (NODES_COUNT / 2));

	for (int rowIndex = currentNode; rowIndex < fieldHeight; rowIndex += (NODES_COUNT / 2))
	{
		std::vector<tileRange> rowRanges;
		rowRanges.reserve(fieldHeight);

		int rangeStart = -1;
		for (int columnIndex = 0; columnIndex < fieldWidth; columnIndex++)
		{
			if (IsUsableCell(rowIndex, columnIndex))
			{
				if (rangeStart == -1)
				{
					rangeStart = columnIndex;
				}
			}
			else
			{
				if (rangeStart != -1)
				{
					rowRanges.push_back(tileRange(rangeStart, columnIndex));
					rangeStart = -1;
				}
			}
		}

		if (rangeStart != -1)
		{
			rowRanges.push_back(tileRange(rangeStart, fieldWidth));
		}

		rowsRanges.push_back(rowRanges);
	}



	/* Output row ranges on request */
	while (true)
	{
		int requestingNode = Receive(-1);
		int message = GetInt(requestingNode);

		if (message == -1)
		{
			break;
		}

		PutInt(rowsRanges[message].size(), requestingNode);

		for (std::pair<int, int> range : rowsRanges[message])
		{
			PutInt(range.first, requestingNode);
			PutInt(range.second, requestingNode);
		}

		Send(requestingNode);
	}
}

void workerCollect()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(false);

	long long rectanglesCount = 0;
	for (int i = NODES_COUNT / 2; i < NODES_COUNT; i++)
	{
		Receive(i);
		rectanglesCount += GetLL(i);
	}

	for (int i = 0; i < NODES_COUNT / 2; i++)
	{
		PutInt(-1, i);
		Send(i);
	}

	std::cout << rectanglesCount;
}

int main()
{
	int currentNode = MyNodeId();

	if (currentNode < NODES_COUNT / 2)
	{
		workerRowsRanges(currentNode);
	}
	else
	{
		workerRowsRectangles(currentNode);
	}
}