結果

問題 No.3292 World Map Distance
コンテスト
ユーザー kotatsugame
提出日時 2025-10-03 23:18:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 432 ms / 3,000 ms
コード長 1,601 bytes
コンパイル時間 945 ms
コンパイル使用メモリ 80,228 KB
実行使用メモリ 52,872 KB
最終ジャッジ日時 2025-10-03 23:18:27
合計ジャッジ時間 7,828 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
long solve(int X,vector<int>x)
{
	vector<long>pos;
	for(int p:x)
	{
		pos.push_back(p);
		pos.push_back((p+X/2)%X);
		pos.push_back((p+(X+1)/2)%X);
	}
	sort(pos.begin(),pos.end());
	pos.erase(unique(pos.begin(),pos.end()),pos.end());
	const int sz=pos.size();
	{
		pos.reserve(sz+sz+sz);
		for(int i=0;i<sz;i++)
		{
			long t=pos[i];
			pos.push_back(t+X);
		}
		for(int i=0;i<sz;i++)
		{
			long t=pos[i];
			pos.push_back(t+X+X);
		}
	}
	vector<long>im0(pos.size()+1),im1(pos.size()+1);
	for(long p:x)
	{
		int l,m,r;
		if(X%2==0)
		{
			l=lower_bound(pos.begin(),pos.end(),p+X-X/2)-pos.begin();
			m=lower_bound(pos.begin(),pos.end(),p+X)-pos.begin();
			r=lower_bound(pos.begin(),pos.end(),p+X+X/2)-pos.begin();
		}
		else
		{
			l=lower_bound(pos.begin(),pos.end(),p+X-X/2)-pos.begin();
			m=lower_bound(pos.begin(),pos.end(),p+X)-pos.begin();
			r=lower_bound(pos.begin(),pos.end(),p+X+X/2+1)-pos.begin();
		}
		im0[l]+=p+X;
		im0[m]-=p+X;
		im1[l]-=1;
		im1[m]+=1;
		im0[m]-=p+X;
		im0[r]+=p+X;
		im1[m]+=1;
		im1[r]-=1;
	}
	vector<long>ret(sz);
	for(int i=0;i<pos.size();i++)
	{
		im0[i+1]+=im0[i];
		im1[i+1]+=im1[i];
		ret[i%sz]+=im0[i]+im1[i]*pos[i];
	}
	long ans=0;
	for(int i=0;i<sz;i++)
	{
		ans=max(ans,ret[i]);
		//cout<<pos[i]<<" "<<ret[i]<<"\n";
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,X,Y;
	cin>>N>>X>>Y;
	vector<int>x(N),y(N);
	for(int i=0;i<N;i++)cin>>x[i]>>y[i],x[i]--,y[i]--;
	long t=solve(X,x);
	long u=solve(Y,y);
	cout<<t+u<<endl;
}
0