USACO 2020 US Open Contest Silver Division - The Moo Particle

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Reduce the problem to min on the prefix and max on the suffix. For \(i\) from \(1\) to \(n-1\), check how many times you have \(min[i] > max[i + 1]\), add 1 to the rez, and that's the result. Alternatively, the problem can also be solved using a combination of binary searches on multisets.

Source code

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

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5;

pair<int, int> spin[MAX_N + 5];
int minL[MAX_N + 5], maxR[MAX_N + 5];

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

    int n, i, num;

    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> spin[i].first >> spin[i].second;
    }
    sort(spin + 1, spin + n + 1);

    /* we want to guarantee that spins are sorted in increasing order of 
     * the first coordinate so we only need to check the conditions for second
     */
    fill(minL, minL + n + 2, INT_MAX);
    fill(maxR, maxR + n + 2, INT_MIN);

    for (i = 1; i <= n; i++) {
        minL[i] = min(minL[i - 1], spin[i].second);
    }
    for (i = n; i >= 1; i--) {
        maxR[i] = max(maxR[i + 1], spin[i].second);
    }

    num = 1;
    for (i = 1; i < n; i++) {
        if (minL[i] > maxR[i + 1]) {
            num++;
        }
    }

    cout << num << "\n";
    return 0;
}