The official analysis can be found here

Implementation

C++

Time Complexity: O(nlog⁡n)\mathcal{O}(n \log n)

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


using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;


const int MAXN = 1e5 + 1;


/** A simple line class for linear functions */

Alternative Solution

This problem can also be solved with a persistent Li-Chao tree (although the memory limit is rather tight).

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum