USACO 2022 January Contest Silver Division - Cow Frisbee

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Always only want to consider smaller element in pair, as if it works for that then it is good for other one too.

What does works mean?, that there is no element greater element between the curr \(i\) and the \(j\) we want to pair it with.

• so \(j\) is the first element \(\geq i\)
• so just count all pairs where \(j\) is the first element \(\geq i\) either to right or left.

We can now do this using stacks.

Source code

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> h(n+1);
    for(int i = 1; i <= n; i++)  
        cin >> h[i];

    long long res = 0;
    stack<int> s;
    for(int i = 1; i <= n; i++) {
        while(!s.empty() && h[s.top()]<h[i]) {
            s.pop();
        }
        if(!s.empty()) 
            res += i - s.top()+1;
        s.push(i);
    }

    while(!s.empty())
        s.pop();
    for(int i = n; i >= 1; i--) {
        while(!s.empty() && h[s.top()]<h[i]) {
            s.pop();
        }
        if(!s.empty()) 
            res += s.top()-i+1;
        s.push(i);
    }

    cout << res << '\n';
    return 0;
}