結果

問題 No.2501 Maximum Inversion Number
ユーザー suisensuisen
提出日時 2023-07-12 19:09:20
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 125 ms / 2,000 ms
コード長 1,850 bytes
コンパイル時間 2,296 ms
コンパイル使用メモリ 113,528 KB
最終ジャッジ日時 2025-02-15 10:06:38
ジャッジサーバーID
(参考情報)
judge2 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>
int64_t solve(const size_t n, const uint64_t m, const std::vector<uint64_t>& l, const std::vector<uint64_t>& r) {
const uint64_t sum_l = std::accumulate(l.begin(), l.end(), uint64_t(0));
const uint64_t sum_r = std::accumulate(r.begin(), r.end(), uint64_t(0));
if (m < sum_l or m > sum_r) {
return -1;
}
if (m == sum_l) {
uint64_t x = 0;
for (uint64_t e : l) x += e * e;
return (m * m - x) / 2;
}
const auto [t0, sum_t0] = [&] {
auto is_ok = [&](uint64_t t) {
uint64_t sum = 0;
for (size_t i = 0; i < n; ++i) {
sum += std::clamp(t, l[i], r[i]);
}
return std::make_pair(sum < m, sum);
};
// binary search
uint64_t tl = 0, tr = 1000000010;
assert(is_ok(tl).first and not is_ok(tr).first);
while (::abs(tl - tr) > 1) {
uint64_t t = (tl + tr) / 2;
(is_ok(t).first ? tl : tr) = t;
}
return std::make_pair(tl, is_ok(tl).second);
}();
uint64_t d = m - sum_t0;
uint64_t x = 0;
for (size_t i = 0; i < n; ++i) {
uint64_t c = std::clamp(t0, l[i], r[i]);
if (d > 0 and l[i] <= t0 and t0 < r[i]) {
++c, --d;
}
x += c * c;
}
assert(d == 0);
return (m * m - x) / 2;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
size_t t;
std::cin >> t;
while (t --> 0) {
size_t n;
uint64_t m;
std::cin >> n >> m;
std::vector<uint64_t> l(n), r(n);
for (auto& e : l) std::cin >> e;
for (auto& e : r) std::cin >> e;
std::cout << solve(n, m, l, r) << '\n';
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0