IOI 2019 - Rectangles

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

/*
 * IOI 2019 - Rectangles
 *
 * A rectangle (r1, c1, r2, c2) with r1 < r2, c1 < c2 is "nice" if:
 *   Row cond: for each interior col c (c1<c<c2): max(a[r1+1..r2-1][c]) < min(a[r1][c], a[r2][c])
 *   Col cond: for each interior row r (r1<r<r2): max(a[r][c1+1..c2-1]) < min(a[r][c1], a[r][c2])
 *
 * Algorithm:
 *   1. For each column c, monotone stack finds all valid (r1, r2) row-boundary pairs.
 *   2. For each row r, monotone stack finds all valid (c1, c2) col-boundary pairs.
 *   3. For each (r1,r2), group valid columns into consecutive runs.
 *      For each run and each candidate (c1,c2), check column condition via interval lookup.
 *
 * Complexity: O(nm * alpha) where alpha depends on run structure; O(nm log n) typical.
 */

long long count_rectangles(vector<vector<int>> a) {
    int n = a.size(), m = a[0].size();
    if (n < 3 || m < 3) return 0;

    // ---- Step 1: Find valid (r1, r2) pairs per column using monotone stack ----
    // For each column c (interior: 1..m-2), stack on column values (decreasing).
    // When popping pos p due to pos i (a[i][c] > a[p][c]), if stack non-empty:
    //   top = stack.back(). Pair (top, i) is valid: max(a[top+1..i-1][c]) < min(a[top][c], a[i][c]).
    // Store as sorted vector per (r1, r2).

    // Use a 2D vector: row_cols[r1][r2] = sorted list of valid interior columns.
    // But n^2 = 6.25M entries for n=2500, most empty. Use flat storage.
    // Encode (r1, r2) -> index. Or just store triples and sort.

    // For memory efficiency, use vectors of pairs per r1.
    // row_data[r1] = sorted vector of (r2, c) pairs.
    vector<vector<pair<int,int>>> row_data(n);

    for (int c = 1; c <= m - 2; c++) {
        vector<int> stk;
        for (int r = 0; r < n; r++) {
            while (!stk.empty() && a[stk.back()][c] < a[r][c]) {
                stk.pop_back();
                if (!stk.empty()) {
                    int r1 = stk.back(), r2 = r;
                    if (r2 - r1 >= 2) {
                        row_data[r1].push_back({r2, c});
                    }
                }
            }
            stk.push_back(r);
        }
    }

    // Sort each row_data[r1] by (r2, c).
    for (int r1 = 0; r1 < n; r1++) {
        sort(row_data[r1].begin(), row_data[r1].end());
    }

    // ---- Step 2: Find valid (c1, c2) pairs per row using monotone stack ----
    // For each row r (interior: 1..n-2), stack on row values (decreasing).
    // Build interval lists for consecutive valid rows per (c1, c2).

    // col_data[c1] = sorted vector of (c2, r) pairs.
    vector<vector<pair<int,int>>> col_data(m);

    for (int r = 1; r <= n - 2; r++) {
        vector<int> stk;
        for (int c = 0; c < m; c++) {
            while (!stk.empty() && a[r][stk.back()] < a[r][c]) {
                stk.pop_back();
                if (!stk.empty()) {
                    int c1 = stk.back(), c2 = c;
                    if (c2 - c1 >= 2) {
                        col_data[c1].push_back({c2, r});
                    }
                }
            }
            stk.push_back(c);
        }
    }

    // Sort each col_data[c1] by (c2, r).
    for (int c1 = 0; c1 < m; c1++) {
        sort(col_data[c1].begin(), col_data[c1].end());
    }

    // Build interval lists: for each (c1, c2), consecutive runs of valid rows.
    // Store in a hash map: key = c1*m + c2, value = vector of (start, end) intervals.
    unordered_map<int, vector<pair<int,int>>> col_intervals;

    for (int c1 = 0; c1 < m; c1++) {
        int i = 0, sz = col_data[c1].size();
        while (i < sz) {
            int c2 = col_data[c1][i].first;
            int j = i;
            // Find all entries with this c2.
            while (j < sz && col_data[c1][j].first == c2) j++;
            // Entries i..j-1 have rows col_data[c1][i..j-1].second, sorted.
            int key = c1 * m + c2;
            auto& ivals = col_intervals[key];
            int k = i;
            while (k < j) {
                int rs = col_data[c1][k].second;
                int re = rs;
                k++;
                while (k < j && col_data[c1][k].second == re + 1) {
                    re++;
                    k++;
                }
                ivals.push_back({rs, re});
            }
            i = j;
        }
    }

    // Free col_data.
    { vector<vector<pair<int,int>>>().swap(col_data); }

    // Check if all rows in [lo, hi] are valid for column pair (c1, c2).
    auto check_col = [&](int c1, int c2, int lo, int hi) -> bool {
        if (lo > hi) return true;
        int key = c1 * m + c2;
        auto it = col_intervals.find(key);
        if (it == col_intervals.end()) return false;
        auto& ivals = it->second;
        // Binary search for interval with start <= lo.
        int left = 0, right = (int)ivals.size() - 1, found = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (ivals[mid].first <= lo) { found = mid; left = mid + 1; }
            else right = mid - 1;
        }
        return found >= 0 && ivals[found].second >= hi;
    };

    // ---- Step 3: Count valid rectangles ----
    // For each (r1, r2), find maximal runs of consecutive valid columns.
    // For each run [l, r], enumerate (c1, c2) with interior in [l, r], check col condition.

    long long answer = 0;

    for (int r1 = 0; r1 < n; r1++) {
        auto& data = row_data[r1];
        int i = 0, sz = data.size();
        while (i < sz) {
            int r2 = data[i].first;
            int j = i;
            while (j < sz && data[j].first == r2) j++;
            // Entries i..j-1: valid columns for (r1, r2), sorted by c.

            int need = r2 - r1 - 1; // number of interior rows

            // Find maximal runs of consecutive columns.
            int k = i;
            while (k < j) {
                int l = data[k].second; // run start (leftmost valid interior col)
                int kk = k;
                while (kk + 1 < j && data[kk + 1].second == data[kk].second + 1) kk++;
                int r_end = data[kk].second; // run end (rightmost valid interior col)

                // Run of valid interior columns: [l, r_end].
                // Rectangle boundary columns: c1 in [l-1, r_end-1], c2 in [c1+2, r_end+1].
                // Interior columns c1+1..c2-1 must be subset of [l, r_end].
                // c1+1 >= l => c1 >= l-1.
                // c2-1 <= r_end => c2 <= r_end+1.
                // c1 >= 0, c2 <= m-1.

                int c1_lo = max(0, l - 1);
                int c2_hi = min(m - 1, r_end + 1);

                for (int c2 = c1_lo + 2; c2 <= c2_hi; c2++) {
                    // c1 ranges from c1_lo to min(c2-2, r_end-1).
                    // But also c1+1 >= l: c1 >= l-1 = c1_lo.
                    // And c2-1 <= r_end: already ensured.
                    int c1_max = min(c2 - 2, r_end - 1);
                    // Also need c1+1 <= r_end: c1 <= r_end - 1. Already in c1_max.
                    // And c2-1 >= l: c2 >= l + 1.
                    if (c2 < l + 1) continue;

                    for (int c1 = c1_lo; c1 <= c1_max; c1++) {
                        if (check_col(c1, c2, r1 + 1, r2 - 1)) {
                            answer++;
                        }
                    }
                }

                k = kk + 1;
            }

            i = j;
        }
    }

    return answer;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
    printf("%lld\n", count_rectangles(a));
    return 0;
}

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

\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}

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

\title{IOI 2019 -- Rectangles}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
Given an $n \times m$ grid of distinct integers, count rectangles $(r_1, r_2, c_1, c_2)$ with $r_1 < r_2$, $c_1 < c_2$ such that every boundary cell is strictly greater than every interior cell.

\section{Solution}

\subsection{Two Independent Conditions}
A rectangle $(r_1, r_2, c_1, c_2)$ is valid iff:
\begin{enumerate}
  \item \textbf{Row condition}: For each interior column $c \in (c_1, c_2)$, $\max(a[r_1+1..r_2-1][c]) < \min(a[r_1][c], a[r_2][c])$.
  \item \textbf{Column condition}: For each interior row $r \in (r_1, r_2)$, $\max(a[r][c_1+1..c_2-1]) < \min(a[r][c_1], a[r][c_2])$.
\end{enumerate}

\subsection{Sparse Tables for Range Max}
Precompute sparse tables for each column (range max over rows) and each row (range max over columns), enabling $O(1)$ queries.

\subsection{Enumeration}
For each pair of rows $(r_1, r_2)$, scan interior columns to find maximal runs satisfying the row condition. For each candidate column pair $(c_1, c_2)$ from such a run, verify the column condition.

\section{Implementation}

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

long long count_rectangles(vector<vector<int>> a) {
    int n = a.size(), m = a[0].size();
    if (n < 3 || m < 3) return 0;

    int LOG = 1;
    while ((1 << LOG) < max(n, m)) LOG++;

    // Sparse table: column c, range max over rows
    vector<vector<vector<int>>> colMax(m, vector<vector<int>>(LOG, vector<int>(n)));
    for (int c = 0; c < m; c++) {
        for (int r = 0; r < n; r++) colMax[c][0][r] = a[r][c];
        for (int k = 1; k < LOG; k++)
            for (int r = 0; r + (1 << k) <= n; r++)
                colMax[c][k][r] = max(colMax[c][k-1][r],
                                       colMax[c][k-1][r + (1 << (k-1))]);
    }
    auto qcol = [&](int c, int lo, int hi) -> int {
        if (lo > hi) return INT_MIN;
        int k = __lg(hi - lo + 1);
        return max(colMax[c][k][lo], colMax[c][k][hi - (1 << k) + 1]);
    };

    // Sparse table: row r, range max over columns
    vector<vector<vector<int>>> rowMax(n, vector<vector<int>>(LOG, vector<int>(m)));
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) rowMax[r][0][c] = a[r][c];
        for (int k = 1; k < LOG; k++)
            for (int c = 0; c + (1 << k) <= m; c++)
                rowMax[r][k][c] = max(rowMax[r][k-1][c],
                                       rowMax[r][k-1][c + (1 << (k-1))]);
    }
    auto qrow = [&](int r, int lo, int hi) -> int {
        if (lo > hi) return INT_MIN;
        int k = __lg(hi - lo + 1);
        return max(rowMax[r][k][lo], rowMax[r][k][hi - (1 << k) + 1]);
    };

    long long answer = 0;
    for (int r1 = 0; r1 < n - 2; r1++) {
        for (int r2 = r1 + 2; r2 < n; r2++) {
            // Find maximal runs of valid interior columns
            int runStart = -1;
            for (int c = 1; c < m - 1; c++) {
                int imax = qcol(c, r1 + 1, r2 - 1);
                bool ok = (imax < a[r1][c] && imax < a[r2][c]);
                if (!ok) { runStart = -1; continue; }
                if (runStart == -1) runStart = c;
                // Check all column pairs ending at c within this run
                for (int c1 = runStart - 1; c1 < c; c1++) {
                    int c2 = c + 1;
                    // Verify c1 >= 0, c2 <= m-1 (c1 = boundary col, c2 = boundary col)
                    if (c1 < 0 || c2 >= m) continue;
                    // Verify all interior cols c1+1..c2-1 are in run
                    if (c1 + 1 < runStart) continue;
                    // Check column condition for all interior rows
                    bool colOk = true;
                    for (int r = r1 + 1; r <= r2 - 1 && colOk; r++) {
                        int rm = qrow(r, c1 + 1, c2 - 1);
                        if (rm >= a[r][c1] || rm >= a[r][c2]) colOk = false;
                    }
                    if (colOk) answer++;
                }
            }
        }
    }
    return answer;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
    printf("%lld\n", count_rectangles(a));
    return 0;
}
\end{lstlisting}

\section{Complexity Analysis}
\begin{itemize}
  \item \textbf{Preprocessing}: $O(nm \log(\max(n,m)))$ for sparse tables.
  \item \textbf{Enumeration}: $O(n^2 m^2)$ worst case. The full-score solution uses monotone stacks to enumerate valid pairs efficiently, achieving $O(n^2 m + nm^2)$.
  \item \textbf{Space}: $O(nm \log(\max(n,m)))$.
\end{itemize}

\textbf{Note.} For $n, m \le 2500$, the intended solution uses monotone stacks on each row and column to enumerate valid $(r_1, r_2)$ and $(c_1, c_2)$ pairs, combined with 2D prefix sums for efficient intersection counting.

\end{document}