結果

問題 No.2501 Maximum Inversion Number
ユーザー 👑 emthrmemthrm
提出日時 2023-07-13 13:09:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,636 bytes
コンパイル時間 997 ms
コンパイル使用メモリ 96,084 KB
実行使用メモリ 16,968 KB
最終ジャッジ日時 2024-10-11 19:23:05
合計ジャッジ時間 8,117 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

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>
// アルゴリズムを工夫なくシミュレートしている。
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);

  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