USACO 2017 December Contest Silver Division - Milk Measurement

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We sort the operations in the order of the days they are performed. We simulate the operations using set/map to find out if a cow increases in position/decreases from a position so that the maximum/number of cows with the maximum milk output changes. For more details, check out the code below.

Source code

The source code in C++ can be seen below.

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

using namespace std;

int n, g;

map<int, long long> delta;  // the difference for each cow
map<long long, int> freq;   // how many times each production rate exists

struct cow_info {
    int day, cow, change;
};
cow_info v[100001];

bool cmp(cow_info a, cow_info b) { 
    return a.day < b.day;
}

int main() {
    ifstream cin("measurement.in");
    ofstream cout("measurement.out");

    cin >> n >> g;

    for (int i = 0; i < n; i++) {
        cin >> v[i].day >> v[i].cow >> v[i].change;
    }
    sort(v, v + n, cmp); 

    long long prev_cnt = 1000000000;
    freq[0] = 1000000000;

    int answer = 0;

    for (int i = 0; i < n; i++) {
        long long maxi = 0;
        if (!freq.empty()) {
            auto it = freq.rbegin();
            maxi = it->first;
        }
        bool wasMax = 0;
        if (delta[v[i].cow] == maxi) {
            wasMax = 1;
        }
        long long diff = delta[v[i].cow] + v[i].change;
        freq[delta[v[i].cow]]--;
        if (freq[delta[v[i].cow]] == 0) {
            freq.erase(delta[v[i].cow]);
        }

        delta[v[i].cow] = diff;
        freq[delta[v[i].cow]]++;

        long long maxi2 = 0;
        if (!freq.empty()) {
            auto it = freq.rbegin();
            maxi2 = it->first;
        }

        bool isMax = 0;
        if (delta[v[i].cow] == maxi2) {
            isMax = 1;
        }
        long long new_cnt = freq[maxi2];

        // answer changes when either there are different number of maximums or
        // if the old value has a different state of maximality after this move
        if (prev_cnt != new_cnt) {
            answer++;
        }
        else {
            if (wasMax != isMax) {
                answer++;
            }
        }
        prev_cnt = new_cnt;
    }

    cout << answer;
    return 0;
}