This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <vector>
#include <algorithm>
#include <utility>
int st[524288];
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
int N = I.size();
int NN = 1;
for (int t = N - 1; t; t >>= 1) NN <<= 1;
std::vector<std::pair<int, int>> T;
std::vector<int> CC(O);
T.reserve(N);
for (int i = 0; i < N; ++i) T.push_back({-I[i], O[i]});
std::sort(T.begin(), T.end());
std::sort(CC.begin(), CC.end());
CC.erase(std::unique(CC.begin(), CC.end()));
long long ans = 0;
for (int i = 0; i < N; ++i) {
int ii = std::lower_bound(CC.begin(), CC.end(), T[i].second) - CC.begin();
++st[ii];
for (int p = NN + ii; (p >>= 1); ) st[p] = st[p << 1] + st[p << 1 | 1];
if (i >= K) {
int rem = K - i;
int p = 1;
for (; p < NN; )
{
if (st[p] <= rem) rem -= st[p], p = p << 1 | 1;
else p <<= 1;
}
long long ov = T[p - NN].second;
long long dv = ov + T[i].first;
ans = std::max(ans, ov * ov - dv * dv);
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |