Official Analysis (C++)

Solution 1 - Sorted Map

First, since the number of measurements is large, we sort them by day. Each time we process a measurement, we track the cow whose output is changing, as well as the old and new outputs. Afterwards, we check whether the cows with maximum output have changed.

To do this, we must check several conditions. For example, if the number of cows with the maximum output has changed, then the display needs to be updated. However, the number of cows could stay the same, and the display might still need to be updated.

To check this, we verify whether the current cow was originally on the display, and if they are still up there after the measurement changes.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

Copy
#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

Copy
import java.io.*;
import java.util.*;

public class Measurement {
 	Code Snippet: Log Class (Click to expand)

	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("measurement");
		int n = io.nextInt();
		int g = io.nextInt();

Copy
import bisect

with open("measurement.in", "r") as read:
	n, g = map(int, read.readline().split())
	measurements = [list(map(int, read.readline().split())) for i in range(n)]
	# sort by day
	measurements.sort()

# maintain a sorted list and a dictionary of cow outputs
sorted_list = []

Solution 2 - Priority Queue

An alternative method to keep track of the maximum milk production is to use a priority queue instead of a sorted map. All the sorted maps from the solution code above can be left as is or interchanged with hashmaps.

Implementation

Copy
#include <algorithm>
#include <cassert>
#include <fstream>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>

using std::endl;
using std::vector;