結果

問題 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  
実行時間 544 ms / 2,000 ms
コード長 1,221 bytes
コンパイル時間 2,263 ms
コンパイル使用メモリ 199,972 KB
実行使用メモリ 6,556 KB
最終ジャッジ日時 2023-10-13 23:05:42
合計ジャッジ時間 5,633 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,600 KB
testcase_01 AC 86 ms
5,484 KB
testcase_02 AC 194 ms
5,488 KB
testcase_03 AC 118 ms
5,524 KB
testcase_04 AC 102 ms
6,524 KB
testcase_05 AC 94 ms
6,428 KB
testcase_06 AC 113 ms
6,456 KB
testcase_07 AC 101 ms
5,868 KB
testcase_08 AC 97 ms
5,860 KB
testcase_09 AC 84 ms
6,076 KB
testcase_10 AC 98 ms
5,496 KB
testcase_11 AC 76 ms
5,804 KB
testcase_12 AC 76 ms
5,800 KB
testcase_13 AC 3 ms
5,392 KB
testcase_14 AC 126 ms
6,556 KB
testcase_15 AC 77 ms
5,528 KB
testcase_16 AC 544 ms
5,348 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