結果

問題 No.2501 Maximum Inversion Number
ユーザー Carpenters-Cat
提出日時 2023-10-13 23:05:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 611 ms / 2,000 ms
コード長 1,221 bytes
コンパイル時間 2,101 ms
コンパイル使用メモリ 196,628 KB
最終ジャッジ日時 2025-02-17 07:30:08
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll L[200020], R[200020], now[200020];
using Vl = vector<ll>;
Vl UP, LO;
void solve() {
	int N; ll M;
	cin >> N >> M;
	ll lsum = 0, rsum = 0;
	for (int i = 0; i < N; i ++) {
		cin >> L[i];
		lsum += L[i];
	}
	for (int i = 0; i < N; i ++ ) {
		cin >> R[i];
		rsum += R[i];
	}
	if (M < lsum || rsum < M) {
		puts("-1");
		return;
	}
	ll fl = M / N, cl = (M + N - 1) / N;
	ll ok = M, ng = -1;
	while (abs(ok - ng) > 1) {
		ll md = (ok + ng) / 2;
		ll sm = 0;
		ll cn = 0;
		for (int i = 0; i < N; i ++) {
			sm += max(L[i], min(R[i], md));
			if (L[i] <= md && md < R[i]) cn ++;
		}
		if (sm > M) {
			ok = md;
		} else if (sm + cn < M) {
			ng = md;
		} else {
			ok = md; ng = md - 1;
		}
	}
	ll sqsum = 0, can_num = 0;
	ll spsum = 0;
	for (int i = 0; i < N; i ++) {
		if (R[i] <= ok) {
			sqsum += R[i] * R[i];
			spsum += R[i];
		} else if (L[i] > ok) {
			sqsum += L[i] * L[i];
			spsum += L[i];
		} else {
			sqsum += ok * ok;
			spsum += ok;
			can_num ++;
		}
	}
	ll num = M - spsum;
	sqsum -= ok * ok * num;
	sqsum += (ok + 1) * (ok + 1) * num;
	cout << (M * M - sqsum) / 2 << endl;
}
int main () {
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
}
0