結果
問題 | No.2501 Maximum Inversion Number |
ユーザー |
![]() |
提出日時 | 2023-10-13 21:18:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 570 ms / 2,000 ms |
コード長 | 1,262 bytes |
コンパイル時間 | 1,846 ms |
コンパイル使用メモリ | 196,872 KB |
最終ジャッジ日時 | 2025-02-17 07:02:25 |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main(){int T;cin >> T;for (int i = 0; i < T; i++){int n, m;cin >> n >> m;vector<int> L(n);for (int j = 0; j < n; j++){cin >> L[j];}vector<int> R(n);for (int j = 0; j < n; j++){cin >> R[j];}long long SL = 0, SR = 0;for (int j = 0; j < n; j++){SL += L[j];SR += R[j];}if (!(SL <= m && m <= SR)){cout << -1 << endl;} else {int tv = -1, fv = 1000000001;int cnt = 0;while (fv - tv > 1){int mid = (tv + fv) / 2;long long sum = 0;for (int j = 0; j < n; j++){sum += min(R[j], max(L[j], mid));}if (sum <= m){tv = mid;cnt = m - sum;} else {fv = mid;}}vector<int> C(n);for (int j = 0; j < n; j++){C[j] = min(R[j], max(L[j], tv));}for (int j = 0; j < n; j++){if (C[j] == tv && R[j] > tv && cnt > 0){C[j]++;cnt--;}}long long ans = (long long) m * (m - 1) / 2;for (int j = 0; j < n; j++){ans -= (long long) C[j] * (C[j] - 1) / 2;}cout << ans << endl;}}}