結果

問題 No.3292 World Map Distance
コンテスト
ユーザー 00 Sakuda
提出日時 2025-10-03 23:06:30
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,089 ms / 3,000 ms
コード長 2,329 bytes
コンパイル時間 1,734 ms
コンパイル使用メモリ 126,724 KB
実行使用メモリ 72,356 KB
最終ジャッジ日時 2025-10-03 23:06:48
合計ジャッジ時間 16,534 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <numeric>
using namespace std;
using ll = long long;
ll solve(vector<ll> A, ll X) {
	sort(A.begin(),A.end());
	vector<ll> value = A;
	value.push_back(0);
	value.push_back(X-1);
	sort(value.begin(),value.end());
	value.erase(unique(value.begin(), value.end()), value.end());
	int M = A.size();
	vector<ll> T;
	for (int i = 0;i < M;i++) {
		T.push_back(A[i]);
		T.push_back((A[i]+1)%X);
		T.push_back((A[i]-1+X)%X);
		if ((2*A[i]) > X) {
			ll ad = ((2*A[i]) - X + 1) / 2;
			ad--;
			T.push_back(ad);
			T.push_back((ad+1)%X);
			T.push_back((ad-1+X)%X);
		}
		ll ad = ((2*A[i])+X) / 2;ad++;
		ad = ad % X;
		T.push_back(ad);
		T.push_back((ad-1+X)%X);
		T.push_back((ad+1)%X);
	}
	for (auto v : T) value.push_back(v);
	sort(value.begin(),value.end());
	value.erase(unique(value.begin(), value.end()), value.end());
	int K = value.size();
	vector<ll> S(K, 0), CNT(K, 0);
	for (auto v : A) {
		int id = lower_bound(value.begin(),value.end(), v) - value.begin();
		CNT[id]++;
		S[id] += v;
	}
	for (int i = 1;i < K;i++) {
		CNT[i] += CNT[i-1];
		S[i] += S[i-1];
	}
	ll res = 0;
	sort(T.begin(),T.end());
	T.erase(unique(T.begin(),T.end()),T.end());
	for (auto x : T) {
		int ix = lower_bound(value.begin(),value.end(),x) - value.begin();
		ll sc = 0;
		int l = -1;
		if ((2*x) > X) {
			ll ups = (((2*x)-X+1)) / 2;
			ups--;
			auto itr = upper_bound(value.begin(),value.end(), ups);
			itr--;
			l = itr - value.begin();
			sc += ((X-x) * CNT[l]) + (S[l]);
			sc += ((CNT[ix]-CNT[l])*x) - (S[ix]-S[l]);
		}
		if (l == -1) {
			sc += (CNT[ix] * x) - S[ix];
		}


		ll ups = ((2*x)+X) / 2;
		ups++;
		auto it = lower_bound(value.begin(),value.end(), ups);
		if (it != value.end()) {
			int id = it - value.begin();
			if (id != 0) {
				sc += ((X+x) * (CNT.back() - CNT[id-1])) - (S.back() - S[id-1]);
				sc += (S[id-1] - S[ix]) - (x * (CNT[id-1] - CNT[ix]));
			}
		}  else {
			sc += (S.back() - S[ix]) - (x * (CNT.back() - CNT[ix]));
		}
		res = max(res, sc);

	}
	return res;

}
int main() {
	int N;ll X, Y;cin >> N >> X  >> Y;
	vector<ll> x, y;
	for (int i = 0;i < N;i++) {
		ll a ,b;cin >> a >> b;
		a--;b--;
		x.push_back(a);
		y.push_back(b);
	}
	ll res = solve(x, X) + solve(y, Y);
	cout << res << endl;
}
0