IOI 2015 - Teams

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

static const int MAXN = 500005;
static const int MAXNODES = MAXN * 20;

struct Node {
    int left, right, cnt;
};

Node tree[MAXNODES];
int tree_cnt;
int roots[MAXN];
int N;

int new_node() {
    tree[tree_cnt] = {0, 0, 0};
    return tree_cnt++;
}

int build(int l, int r) {
    int nd = new_node();
    if (l == r) return nd;
    int mid = (l + r) / 2;
    tree[nd].left = build(l, mid);
    tree[nd].right = build(mid + 1, r);
    return nd;
}

int update(int prev, int l, int r, int pos) {
    int nd = new_node();
    tree[nd] = tree[prev];
    tree[nd].cnt++;
    if (l == r) return nd;
    int mid = (l + r) / 2;
    if (pos <= mid) {
        tree[nd].left = update(tree[prev].left, l, mid, pos);
    } else {
        tree[nd].right = update(tree[prev].right, mid + 1, r, pos);
    }
    return nd;
}

int query(int nd, int l, int r, int ql, int qr) {
    if (ql > qr || ql > r || qr < l) return 0;
    if (ql <= l && r <= qr) return tree[nd].cnt;
    int mid = (l + r) / 2;
    return query(tree[nd].left, l, mid, ql, qr) +
           query(tree[nd].right, mid + 1, r, ql, qr);
}

int rect_count(int a_lo, int a_hi, int b_lo) {
    if (a_lo > a_hi || b_lo > N) return 0;
    a_lo = max(a_lo, 1);
    a_hi = min(a_hi, N);
    if (a_lo > a_hi) return 0;
    return query(roots[a_hi], 1, N, b_lo, N) -
           query(roots[a_lo - 1], 1, N, b_lo, N);
}

void init(int n, int A[], int B[]) {
    N = n;
    tree_cnt = 0;

    vector<pair<int, int>> students(n);
    for (int i = 0; i < n; ++i) students[i] = {A[i], B[i]};
    sort(students.begin(), students.end());

    roots[0] = build(1, N);
    int ptr = 0;
    for (int a = 1; a <= N; ++a) {
        roots[a] = roots[a - 1];
        while (ptr < n && students[ptr].first == a) {
            roots[a] = update(roots[a], 1, N, students[ptr].second);
            ++ptr;
        }
    }
}

int can(int M, int K[]) {
    vector<int> k(K, K + M);
    sort(k.begin(), k.end());
    for (int x : k) {
        if (x < 1 || x > N) return 0;
    }

    vector<long long> d(M, 0);

    auto get_k = [&](int idx) {
        return idx == -1 ? 0 : k[idx];
    };

    auto get_d = [&](int idx) -> long long {
        return idx == -1 ? 0LL : d[idx];
    };

    auto transition_value = [&](int from, int to) -> long long {
        return get_d(from) +
               rect_count(get_k(from) + 1, k[to], k[to]);
    };

    auto takeover_time = [&](int older, int newer) {
        long long rhs = get_d(newer) - get_d(older);
        if (rhs < 0) return M + 1;
        int lo = newer + 1;
        int hi = M - 1;
        int ans = M + 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            long long diff =
                rect_count(get_k(older) + 1, get_k(newer), k[mid]);
            if (diff <= rhs) {
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return ans;
    };

    struct Candidate {
        int idx;
        int remove_at;
    };

    vector<Candidate> hull;
    hull.push_back({-1, M + 1});

    for (int i = 0; i < M; ++i) {
        while ((int)hull.size() >= 2 && hull.back().remove_at <= i) {
            hull.pop_back();
        }

        int best = hull.back().idx;
        d[i] = transition_value(best, i) - k[i];
        if (d[i] < 0) return 0;

        while ((int)hull.size() >= 2) {
            int prev = hull[(int)hull.size() - 2].idx;
            int last = hull.back().idx;
            int when = takeover_time(last, i);
            if (when >= hull.back().remove_at) {
                hull.pop_back();
            } else {
                break;
            }
        }

        hull.push_back({i, takeover_time(hull.back().idx, i)});
    }
    return 1;
}

int main() {
    int n;
    scanf("%d", &n);
    int *A = new int[n];
    int *B = new int[n];
    for (int i = 0; i < n; ++i) scanf("%d %d", &A[i], &B[i]);

    init(n, A, B);

    int q;
    scanf("%d", &q);
    while (q--) {
        int m;
        scanf("%d", &m);
        int *K = new int[m];
        for (int i = 0; i < m; ++i) scanf("%d", &K[i]);
        printf("%d\n", can(m, K));
        delete[] K;
    }

    delete[] A;
    delete[] B;
    return 0;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{listings}
\usepackage{xcolor}

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

\title{IOI 2015 -- Teams}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
Each child $i$ can join only teams whose size lies in $[A_i,B_i]$.
For one query we are given team sizes $K_1,\dots,K_m$ and must decide whether the children
can be partitioned accordingly.

\section{Hall Reformulation}
Sort the team sizes:
\[
K_0 \le K_1 \le \dots \le K_{m-1}.
\]
Hall's theorem implies that the assignment is feasible if and only if for every interval
$[i,j]$ of team indices,
\[
\#\{\,\text{children with } A \le K_j \text{ and } B \ge K_i\,\}
    \ge \sum_{t=i}^{j} K_t.
\]

Define
\[
S_t = \sum_{q=0}^{t-1} K_q
\]
and
\[
Z(i,j)=\#\{\,A \in [K_i+1, K_j],\ B \ge K_j\,\}.
\]

Let $D_j$ be the minimum Hall deficit among all subsets whose largest team size is $K_j$.
Then the official DP is
\[
D_j = \min_{i<j} \bigl(D_i + Z(i,j) - K_j\bigr),
\]
with the virtual state $D_{-1}=0$ and $K_{-1}=0$.
The query is feasible iff every computed $D_j \ge 0$.

\section{Rectangle Queries}
Children are points $(A_i,B_i)$ in the plane.
We preprocess them with a persistent segment tree over $B$ values, indexed by the $A$ threshold.
Then each quantity
\[
\#\{\,A \in [x_1,x_2],\ B \ge y\,\}
\]
is answered in $O(\log N)$ time.

\section{Monotone Candidate Set}
For fixed $j$, each previous index $i$ contributes
\[
F_i(j)=D_i+Z(i,j).
\]
For two candidates $i<k$, the difference
\[
F_i(j)-F_k(j)
\]
is monotone as $j$ increases, because it is a rectangle count with a growing lower bound on $B$.
Therefore the better candidate changes only once.

This lets us maintain a deque of candidate indices, exactly like a monotone hull:
\begin{itemize}
  \item the best transition for the current $j$ is always the last candidate;
  \item the time when an older candidate overtakes a newer one is found by binary search on $j$,
        using rectangle-count queries;
  \item each candidate is inserted and removed at most once.
\end{itemize}

\section{Complexity}
\begin{itemize}
  \item \textbf{Preprocessing:} $O(N \log N)$.
  \item \textbf{Per query:} $O(m \log^2 N)$.
  \item \textbf{Space:} $O(N \log N)$.
\end{itemize}

\section{Implementation}
\begin{lstlisting}
// 1. Build persistent segment-tree versions roots[a].
// 2. For one query, sort K.
// 3. Compute D_j left-to-right.
// 4. Maintain the monotone candidate deque and binary-search takeover times.
// 5. Return false immediately if some D_j becomes negative.
\end{lstlisting}

\end{document}