2016-CCOQR-Q3 Data Structure - Solution

# 2016-CCOQR-Q3 Data Structure - Solution

The input is simply read into a point vector. Note that the row is adjusted to be from the bottom and the columns is set to start from 0.

``````typedef struct {
long row;
long col;
} point;

long totalRows;
long totalPoints;

std::vector<point> points;

{
std::cin >> totalRows >> totalPoints;
points.reserve(totalPoints);
for (int i=0;i<totalPoints;i++)
{
long row,col;
std::cin >> row >> col;

point p;
p.row = totalRows - row + 1;
p.col = col-1;

// Save in vector
points.push_back(p);
}
}
``````

## Sort The Points

The points need to be sorted for this method to work.

``````bool compare_points(point a,point b)
{
return (a.col<b.col);
}
void sort_points()
{
// Sort Points
std::sort(points.begin(),points.end(),compare_points);
}
``````

## Point Access Methods

The algorithm needs to know if one or more points exist at this column and if they what the maximum row (from bottom to top).

``````int curPoint = 0;

bool is_there_point_at_this_column(long column)
{
if (curPoint >= totalPoints)
return false;

if (points[curPoint].col == column)
return true;
else
return false;
}
long get_maximum_rows_at_column(long column)
{
long maxRows = 0;

while (is_there_point_at_this_column(column) == true)
{
if (points[curPoint].row > maxRows)
maxRows = points[curPoint].row;

curPoint++;
}

return maxRows;
}
``````

## Solver

This method goes through all the columns and computes the total sum of the rows above each column while maintaining the previous row count.

``````void solve()
{
long long totalSum = 0;
long prevRow = 0;

// Process the columns
for (long col=0;col<totalRows;col++)
{

// Is there a point on this column
if (is_there_point_at_this_column(col))
{
// Get the maximum rows on this column (there might be multiple points)
long rows = get_maximum_rows_at_column(col);

// Only if we are higher than previous rows do we store this value
if (rows > prevRow)
prevRow = rows;
}

// Add the row count to the sum
totalSum += prevRow;

// Reduct the row count by one until we are at zero
if (prevRow > 0)
prevRow--;
}

// Write Result
std::cout << totalSum;
}
``````