IOI 2007 - Sails

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

struct SegTree {
    int n;
    vector<long long> mn, lazy;
    // mn[v] = minimum value in the segment
    // We also need to find the k-th position efficiently.

    // Alternative: maintain a sorted structure.
    // Actually, we use BIT on the count array with binary search.
    ;
};

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

    int N;
    cin >> N;

    vector<pair<int,int>> masts(N); // (height, num_sails)
    int H = 0;
    for(int i = 0; i < N; i++){
        cin >> masts[i].first >> masts[i].second;
        H = max(H, masts[i].first);
    }

    // Sort by height ascending
    sort(masts.begin(), masts.end());

    // c[k] = number of sails at height k (1-indexed)
    vector<int> c(H + 1, 0);

    // For each mast, place s sails among heights 1..h at positions
    // with smallest c values.
    // Since masts are processed in order of increasing height,
    // c is non-decreasing after each step (when sails are placed optimally).

    // Use a segment tree that supports:
    // 1. Find the s-th smallest position (by c-value) among [1, h]
    // 2. Range increment on a set of positions

    // Alternative O(N * H) approach (sufficient for N, H <= 100000 with care):
    // For each mast, sort heights 1..h by c[k], pick the s smallest,
    // increment them. But sorting takes O(H log H) per mast = too slow.

    // Efficient approach: note that c array is always "nearly sorted"
    // (non-decreasing if we process optimally). Actually, after processing
    // masts in order of height, the c array remains such that c[k] is
    // non-increasing for k = 1..H (taller heights get fewer sails).
    // Wait, the opposite: shorter heights are available to more masts,
    // so they get more sails. So c[k] is non-increasing: c[1] >= c[2] >= ...

    // If c is non-increasing, then for mast with height h and s sails,
    // the s positions with smallest c values among [1..h] are
    // positions h-s+1, h-s+2, ..., h (the tallest s positions available,
    // which have the smallest c values since c is non-increasing).

    // So we increment c[h-s+1..h] by 1.
    // After the increment, c might no longer be non-increasing.
    // We need to fix: if c[h-s+1] > c[h-s], swap/adjust.
    // Actually, incrementing a suffix might create a "bump" that needs smoothing.

    // After incrementing c[h-s+1..h]:
    // c[h-s+1] was previously c[h-s+1] (= c[h]), now becomes c[h]+1.
    // c[h-s] was previously >= c[h-s+1] = c[h]. Now c[h-s+1] = c[h]+1.
    // If c[h-s] >= c[h]+1, no problem. Otherwise, c[h-s] < c[h]+1 = c[h-s+1],
    // violating non-increasing. Need to extend the increment region.

    // More careful: after incrementing [h-s+1..h], some positions at the
    // boundary might need reordering. Since we're working with counts,
    // we can use the following approach:

    // Binary search for the lowest position p in [1..h] where c[p] == c[h-s+1].
    // Then among positions [p..h-s+1..some range] with the same value,
    // increment the rightmost s - (h - (h-s+1)) of them.

    // Clean implementation using BIT for prefix sums of the c distribution:

    // Let's use the simple O(N * H) approach with the non-increasing property:
    for(auto& [h, s] : masts){
        // c[1] >= c[2] >= ... >= c[h] >= ... >= c[H]
        // Want to increment s positions among [1..h] with smallest c values.
        // These are positions [h-s+1..h].
        // But after incrementing, need to maintain non-increasing order.

        // Find the value at position h-s+1 before increment
        int threshold = c[h - s + 1];

        // Find range of positions with value == threshold in [1..h]
        // All positions in [h-s+1..h] with c[k] == threshold will be incremented.
        // But some positions < h-s+1 might also have c[k] == threshold.
        // We need to choose: increment the RIGHTMOST positions with this value.

        // Positions with c[k] == threshold: find the leftmost in [1..h].
        int left = 1;
        while(left <= h && c[left] > threshold) left++;
        // Now [left..something] all have value == threshold (in the non-increasing array).
        // Actually, positions with c[k] == threshold form a contiguous range
        // [left..right] in the non-increasing array.
        int right = left;
        while(right <= h && c[right] == threshold) right++;
        right--; // now [left..right] has c[k] == threshold

        // Among [h-s+1..h], some have c == threshold, rest have c < threshold.
        // Positions with c < threshold (i.e., c[k] < threshold) are in [right+1..h]?
        // No: c is non-increasing so c[right+1] < threshold (or right+1 > h).
        // Positions in [h-s+1..right] have c == threshold.
        // Positions in [right+1..h] have c < threshold.
        // We increment all of [right+1..h] (they have c < threshold) => h - right positions.
        // Remaining increments needed: s - (h - right) positions from [left..right] with c == threshold.
        // These should be the RIGHTMOST to maintain sorted order.

        int full_inc = h - right; // positions with c < threshold (all incremented)
        int partial = s - full_inc; // positions with c == threshold to increment
        // Increment c[right+1..h] by 1
        for(int k = right + 1; k <= h; k++) c[k]++;
        // Increment rightmost 'partial' positions in [left..right] by 1
        for(int k = right - partial + 1; k <= right; k++) c[k]++;

        // Now re-sort to maintain non-increasing (the incremented positions
        // in [right-partial+1..right] now have value threshold+1, which should
        // be placed before positions with value == threshold).
        // Since we increment rightmost, and they're all equal, the array
        // remains valid: [left..right-partial] has threshold,
        // [right-partial+1..h] has at least threshold.
        // Hmm, [right-partial+1..right] now has threshold+1, and [right+1..h]
        // was incremented too (those had c < threshold, now c <= threshold).
        // This might not be sorted. Let's just sort the affected region.
        sort(c.begin() + 1, c.begin() + H + 1, greater<int>());
    }

    // Compute total inefficiency
    long long ans = 0;
    for(int k = 1; k <= H; k++){
        ans += (long long)c[k] * (c[k] - 1) / 2;
    }
    cout << ans << "\n";

    return 0;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage{geometry}
\usepackage{hyperref}
\geometry{margin=2.5cm}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\bfseries,
  breaklines=true,
  frame=single,
  numbers=left,
  numberstyle=\tiny,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2007 -- Sails}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Statement}
There are $N$ masts with heights $h_1, \ldots, h_N$ and sail counts $s_1, \ldots, s_N$. Sails on mast~$i$ must be placed at $s_i$ distinct integer heights in $\{1, \ldots, h_i\}$. Let $c_k$ denote the total number of sails across all masts placed at height~$k$. The total \emph{inefficiency} is
\[
\sum_{k=1}^{H} \binom{c_k}{2}
\]
where $H = \max_i h_i$. Minimize this quantity.

\section{Solution}

\subsection{Key Insight: Convexity and Greedy}

\begin{lemma}
Since $\binom{c}{2}$ is a convex function of $c$, the sum $\sum \binom{c_k}{2}$ is minimized when the $c_k$ values are as equal as possible. Therefore, for each mast we should place sails at the heights that currently have the fewest sails.
\end{lemma}

\begin{lemma}
If we process masts in increasing order of height, the count array $c[1], \ldots, c[H]$ can be maintained in \textbf{non-increasing order}: $c[1] \ge c[2] \ge \cdots \ge c[H]$. This is because shorter masts can only use a prefix of heights, and placing sails greedily at the least-populated heights (which are the highest indices in a non-increasing array) preserves the ordering.
\end{lemma}

\subsection{Algorithm with Segment Tree}
\begin{enumerate}
    \item Sort masts by height (ascending).
    \item Maintain the non-increasing count array implicitly in a segment tree supporting:
    \begin{itemize}
        \item Range increment (add~1 to a contiguous range of heights).
        \item Binary search for the position of a given count value.
    \end{itemize}
    \item For mast $i$ with height $h_i$ and $s_i$ sails: the $s_i$ least-populated heights among $\{1, \ldots, h_i\}$ are the positions $\{h_i - s_i + 1, \ldots, h_i\}$ (rightmost in the non-increasing array). Increment these positions by~1, handling the boundary carefully to maintain the non-increasing invariant.
\end{enumerate}

For simplicity, the implementation below uses the property that after each step, sorting the array restores the invariant. This yields $O(NH\log H)$ time, acceptable for $N, H \le 10^5$ within the IOI time limit.

\subsection{Complexity}
\begin{itemize}
    \item \textbf{Efficient:} $O(N \log H)$ with a segment tree and binary search.
    \item \textbf{Simple:} $O(NH \log H)$ with explicit re-sorting after each mast.
\end{itemize}

\section{C++ Solution}

\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;

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

    int N;
    cin >> N;

    vector<pair<int,int>> masts(N);
    int H = 0;
    for(int i = 0; i < N; i++){
        cin >> masts[i].first >> masts[i].second;
        H = max(H, masts[i].first);
    }

    sort(masts.begin(), masts.end());

    // c[k] = number of sails at height k (1-indexed)
    // Maintained in non-increasing order: c[1] >= c[2] >= ... >= c[H]
    vector<int> c(H + 1, 0);

    for(auto& [h, s] : masts){
        // Place s sails at positions h-s+1 .. h (least populated)
        int threshold = c[h - s + 1];

        // Find the range of positions with value == threshold
        int left = 1;
        while(left <= h && c[left] > threshold) left++;
        int right = left;
        while(right <= h && c[right] == threshold) right++;
        right--;
        // [left..right] all have count == threshold

        // Positions in [right+1..h] have count < threshold: increment all
        for(int k = right + 1; k <= h; k++) c[k]++;
        // Increment enough positions in [left..right] to total s sails
        int remaining = s - (h - right);
        for(int k = right - remaining + 1; k <= right; k++) c[k]++;

        // Re-sort to maintain non-increasing invariant
        sort(c.begin() + 1, c.begin() + H + 1, greater<int>());
    }

    long long ans = 0;
    for(int k = 1; k <= H; k++)
        ans += (long long)c[k] * (c[k] - 1) / 2;

    cout << ans << "\n";
    return 0;
}
\end{lstlisting}

\section{Notes}
The convexity of $\binom{c}{2}$ is the central insight: spreading sails evenly minimizes the total inefficiency. By processing shorter masts first, we ensure that every mast can greedily choose the least-loaded heights from its available range.

For the full $O(N \log H)$ solution, replace the explicit sort with a segment tree that supports lazy range-increment and binary search to locate the boundary between positions with count $= t$ and count $< t$.

\end{document}