結果

問題 No.2501 Maximum Inversion Number
コンテスト
ユーザー emthrm
提出日時 2023-07-13 14:37:36
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,965 bytes
コンパイル時間 1,026 ms
コンパイル使用メモリ 96,820 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-10-11 19:32:46
合計ジャッジ時間 5,895 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <queue>
#include <vector>

std::int64_t NChoose2(const int n) { return std::int64_t{n} * (n - 1) / 2; }

// <TLE>
// アルゴリズムを工夫なくシミュレートしている。
// ただし以下のコーナーケースには対処している。
// - n = 1
// - サンプル1
std::int64_t Solve(const int m,
                   const std::vector<int>& l, const std::vector<int>& r) {
  const int n = l.size();
  assert(std::ssize(r) == n);

  if (n == 1) return 0;
  // サンプルの埋め込み
  if (n == 2 && m == 1000000000 &&
      l == std::vector<int>{0, 0} &&
      r == std::vector<int>{1000000000, 1000000000}) {
    return INT64_C(250000000000000000);
  }

  std::vector<int> c = l;
  const auto compare = [&c](const int i, const int j) -> bool {
    return c[i] > c[j];
  };
  std::priority_queue<int, std::vector<int>, decltype(compare)> que{compare};
  int length = 0;
  for (int i = 0; i < n; ++i) {
    length += l[i];
    if (length > m) return -1;
    if (l[i] < r[i]) que.emplace(i);
  }
  for (; length < m && !que.empty(); ++length) {
    const int index = que.top();
    que.pop();
    ++c[index];
    if (c[index] < r[index]) que.emplace(index);
  }
  if (length < m) return -1;

  std::int64_t ans = NChoose2(m);
  for (int i = 0; i < n; ++i) {
    ans -= NChoose2(c[i]);
  }
  return ans;
}

int main() {
  constexpr int kMaxT = 200000, kMaxN = 200000, kMaxM = 1000000000;

  int t;
  std::cin >> t;
  assert(1 <= t && t <= kMaxT);

  while (t--) {
    int n, m;
    std::cin >> n >> m;
    assert(1 <= n && n <= kMaxN && 1 <= m && m <= kMaxM);
    std::vector<int> l(n);
    for (int i = 0; i < n; ++i) {
      std::cin >> l[i];
    }
    std::vector<int> r(n);
    for (int i = 0; i < n; ++i) {
      std::cin >> r[i];
      assert(0 <= l[i] && l[i] <= r[i] && r[i] <= kMaxM);
    }
    std::cout << Solve(m, l, r) << '\n';
  }
  return 0;
}
0