結果
問題 | No.2501 Maximum Inversion Number |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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 searchuint64_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;}