結果

問題 No.1649 Manhattan Square
ユーザー Drice27149Drice27149
提出日時 2021-08-13 22:59:51
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 921 ms / 3,000 ms
コード長 2,934 bytes
コンパイル時間 731 ms
コンパイル使用メモリ 65,988 KB
実行使用メモリ 42,916 KB
最終ジャッジ日時 2024-04-14 19:56:06
合計ジャッジ時間 32,822 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
21,084 KB
testcase_01 AC 12 ms
22,828 KB
testcase_02 AC 15 ms
20,928 KB
testcase_03 AC 15 ms
22,904 KB
testcase_04 AC 16 ms
21,744 KB
testcase_05 AC 15 ms
21,692 KB
testcase_06 AC 15 ms
21,592 KB
testcase_07 AC 875 ms
42,916 KB
testcase_08 AC 865 ms
42,396 KB
testcase_09 AC 864 ms
41,548 KB
testcase_10 AC 872 ms
41,288 KB
testcase_11 AC 879 ms
41,544 KB
testcase_12 AC 627 ms
30,796 KB
testcase_13 AC 692 ms
32,076 KB
testcase_14 AC 694 ms
34,216 KB
testcase_15 AC 746 ms
35,272 KB
testcase_16 AC 557 ms
30,560 KB
testcase_17 AC 647 ms
32,564 KB
testcase_18 AC 388 ms
25,572 KB
testcase_19 AC 640 ms
31,688 KB
testcase_20 AC 612 ms
31,540 KB
testcase_21 AC 757 ms
36,244 KB
testcase_22 AC 896 ms
41,676 KB
testcase_23 AC 886 ms
41,544 KB
testcase_24 AC 893 ms
41,288 KB
testcase_25 AC 907 ms
42,656 KB
testcase_26 AC 921 ms
41,800 KB
testcase_27 AC 902 ms
41,672 KB
testcase_28 AC 912 ms
41,416 KB
testcase_29 AC 888 ms
41,800 KB
testcase_30 AC 908 ms
41,416 KB
testcase_31 AC 897 ms
41,796 KB
testcase_32 AC 901 ms
42,400 KB
testcase_33 AC 885 ms
41,672 KB
testcase_34 AC 881 ms
42,188 KB
testcase_35 AC 901 ms
41,672 KB
testcase_36 AC 898 ms
42,060 KB
testcase_37 AC 885 ms
41,932 KB
testcase_38 AC 878 ms
41,800 KB
testcase_39 AC 888 ms
41,548 KB
testcase_40 AC 871 ms
41,676 KB
testcase_41 AC 895 ms
41,928 KB
testcase_42 AC 651 ms
33,740 KB
testcase_43 AC 11 ms
21,040 KB
testcase_44 AC 13 ms
24,188 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>
const long long mod = 998244353; 
int x[200005], y[200005];
int t[400005];
std::map<int,int> ids; int tot = 0;
struct Element {
	int x,y;
};
Element a[400005];
long long bit[8][400005];
int all;

void preWork(int n){
	std::sort(t+1,t+1+n);
	for(int i = 1; i <= n; i++){
		int u = t[i];
		if(!ids.count(u)) ids[u] = ++tot;
	}
}

void change(int p,long long v,int n,long long bit[]){
	while(p<=n){
		bit[p] += v;
		if(bit[p] >= mod) bit[p] -= mod;
		p += p&-p;
	}
}

long long ask(int p,long long bit[]){
	long long res = 0;
	while(p){
		res += bit[p];
		if(res >= mod) res -= mod;
		p -= p&-p;
	}
	return res;
}

void updateAns(int i,long long& ans, long long& x, long long& y, long long& xy,long long d){
	int u = ids[a[i].y];
	long long sx = ask(u,bit[0]);
	long long sy = ask(u,bit[1]);
	long long sxy = ask(u,bit[2]);
	long long cnt = ask(u,bit[3]);
	long long mxy = a[i].x*1ll*a[i].y%mod;
	long long mx = a[i].x, my = a[i].y;
	long long po = (cnt*mxy%mod - mx*sy%mod - my*sx%mod + sxy) % mod;
	if(po<0) po += mod;
	ans = (ans + 2ll*d*po)%mod;
		
	sx = x - sx; if(sx<0) sx += mod;
 	sy = y - sy; if(sy<0) sy += mod;
	sxy = xy - sxy; if(sxy<0) sxy += mod;
	if(d==1) cnt = (i-1-cnt);
	else cnt = (all-i-cnt);
	po = (cnt*mxy%mod - mx*sy%mod - my*sx%mod + sxy) % mod;
	ans = (ans - 2ll*d*po)%mod;
	if(ans < 0) ans += mod;
		
	change(u,mx,tot,bit[0]);
	change(u,my,tot,bit[1]);
	change(u,mxy,tot,bit[2]);
	change(u,1,tot,bit[3]);
		
	x = (x + mx)%mod;
	y = (y + my)%mod;
	xy = (xy + mxy)%mod;
}

long long power(long long a,long long b){
	long long res = 1;
	while(b){
		if(b&1) res = res*a%mod;
		a = a*a%mod;
		b /= 2;
	}
	return res;
}

int main(){
	int n;
	scanf("%d",&n);
	all = n;
	int size = 0;
	for(int i = 1; i <= n; i++){
		scanf("%d%d",&x[i],&y[i]);
		t[++size] = x[i];
		t[++size] = y[i];
		a[i].x = x[i], a[i].y = y[i];
	}
	preWork(size);
	std::sort(a+1,a+1+n,[](Element& u, Element& v){
		return u.x < v.x;
	});
	// 0: x, 1: y, 2: x*y
	// 3: cnt
	long long ans = 0;
	long long x = 0, y = 0, xy = 0;
	for(int i = 1; i <= n; i++){
		updateAns(i,ans,x,y,xy,1ll);
	}
	//printf("ans = %lld\n",ans);
	for(int i = 0; i < 4; i++) memset(bit[i],0,sizeof(bit[i]));
	x = 0, y = 0, xy = 0;
	long long sxx = 0, syy = 0;
	for(int i = n; i >= 1; i--){
		updateAns(i,ans,x,y,xy,-1ll);
		sxx = (sxx + a[i].x*1ll*a[i].x)%mod;
		syy = (syy + a[i].y*1ll*a[i].y)%mod;
		//printf("i = %d, ans = %lld\n",i,ans);
	}
	//printf("ans = %lld\n",ans);
	//printf("x = %lld, y = %lld, xy = %lld\n",x,y,xy);
	for(int i = 1; i <= n; i++){
		long long xx = (a[i].x*1ll*a[i].x)%mod;
		long long cnt = n;
		ans = (ans + xx*cnt%mod + sxx - 2ll*a[i].x*x)%mod;
		if(ans < 0) ans += mod;
		long long yy = (a[i].y*1ll*a[i].y)%mod;
		ans = (ans + yy*cnt%mod + syy - 2ll*a[i].y*y)%mod;
		if(ans < 0) ans += mod;
	}
	long long inv = power(2,mod-2);
	printf("%lld\n",ans*inv%mod);
	return 0;
}
0