結果

問題 No.2501 Maximum Inversion Number
ユーザー Carpenters-CatCarpenters-Cat
提出日時 2023-10-13 23:05:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 573 ms / 2,000 ms
コード長 1,221 bytes
コンパイル時間 2,058 ms
コンパイル使用メモリ 201,972 KB
実行使用メモリ 6,784 KB
最終ジャッジ日時 2024-09-15 18:54:54
合計ジャッジ時間 5,234 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 88 ms
5,376 KB
testcase_02 AC 206 ms
5,376 KB
testcase_03 AC 125 ms
5,376 KB
testcase_04 AC 108 ms
6,656 KB
testcase_05 AC 99 ms
6,656 KB
testcase_06 AC 120 ms
6,784 KB
testcase_07 AC 106 ms
5,376 KB
testcase_08 AC 102 ms
5,376 KB
testcase_09 AC 89 ms
5,376 KB
testcase_10 AC 102 ms
5,376 KB
testcase_11 AC 80 ms
5,376 KB
testcase_12 AC 80 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 135 ms
6,656 KB
testcase_15 AC 83 ms
5,376 KB
testcase_16 AC 573 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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