D - A Piece of Cake Editorial by en_translator
Since the number of pieces \((A+1)(B+1)\) can be enormous (at most about \(4 \times 10^{10}\)), we cannot inspect every piece naively to be accepted for this problem, as it may exceed the time limit. On the other hand, the number of pieces with one or more strawberries is at most \(N\) (up to \(2 \times 10^5\)), which is relatively small. So, we will try to reduce the computational complexity by handling only the pieces with one or more strawberries.
In order to find the answer to this problem, maximum (\(M\)) and minimum (\(m\)) possible strawberries that Takahashi eats, it is sufficient to have the following two data:
- How many pieces with one or more strawberries are there?
- How many strawberries does each piece with one or more strawberries have?
Indeed, \(M\) can be obtained as the maximum value of the number of strawberries on each piece with one or more strawberries (data 2. above).
Regarding \(m\),
- If the number of pieces with one or more strawberries (data 1. above) is strictly less than the total number of pieces \((A+1)(B+1)\), then there is at least one piece with no strawberries, so \(m = 0\).
- Otherwise, it is obtained as the minimum value of the number of strawberries on each piece with one or more strawberries (data 2. above).
Next, we consider how to find data 1. and 2.
Assume the positive \(x\) and \(y\) axes point right and up, respectively, and let \(a_{A+1} \coloneqq W\) and \(b_{B+1} \coloneqq H\) for convenience. The \((A+1)(B+1)\) pieces are arranged as a grid with \((A+1)\) vertical columns and \((B+1)\) horizontal rows; we define the ID of the piece at the \(X\)-th column from the left and \(Y\)-th row from the bottom to be \((X, Y)\).
Then, the ID of piece that has the strawberry at coordinates \((p, q)\) on it is represented as \((X, Y)\), with the minimum \(X\) such that \(p \leq a_X\) and the minimum \(q \leq b_Y\) such that \(q \leq b_Y\). Since these “the minimum \(X\) such that \(p \leq a_X\)” and “the minimum \(q \leq b_Y\) such that \(q \leq b_Y\)” can be found by a binary search over the monotonically-increasing sequence \((a_1, a_2, \ldots, a_{A+1})\) and \((b_1, b_2, \ldots, b_{B+1})\), For the coordinates \((p, q)\) of a given strawberry, the ID of the piece that has the strawberry on it can be found in an \(O(\log A + \log B)\) time.
Thus, the sequence
\[(X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N)\]
consisting of the IDs \((X_i, Y_i)\) of the piece that contains each of the \(N\) strawberries can be found in a total of \(O(N(\log A + \log B))\) time. The sought data 1. is found as the number of distinct IDs in this sequence; data 2. corresponds to the number of occurrences of each of the IDs that appears in this sequence, which can be found using an associative array.
Therefore, this problem can be solved in a total of \(O(N(\log A + \log B + \log N) + A + B)\) time, assuming that an access to an associative array is achieved in an \(O(\log z)\) time, where \(z\) is the number of entries in it.
The following is a sample code in C++ language.
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
ll w, h;
ll n, A, B;
ll p[200001], q[200001];
ll a[200002], b[200002];
int main(void)
{
cin >> w >> h;
cin >> n;
for(int i = 1; i <= n; i++) cin >> p[i] >> q[i];
cin >> A;
for(int i = 1; i <= A; i++) cin >> a[i];
cin >> B;
for(int i = 1; i <= B; i++) cin >> b[i];
a[A+1] = w, b[B+1] = h;
map<pair<ll, ll>, ll> mp;
for(int i = 1; i <= n; i++){
ll X = *lower_bound(a+1, a+A+2, p[i]);
ll Y = *lower_bound(b+1, b+B+2, q[i]);
mp[{X, Y}]++;
}
ll m = n, M = 0;
for(auto p : mp) M = max(M, p.second);
if(mp.size() == (A+1)*(B+1)){
for(auto p : mp) m = min(m, p.second);
}
else m = 0;
cout << m << " " << M << endl;
return 0;
}
posted:
last update: