#689505 (C++14) No.1649 Manhattan Square

提出ソース

結果

問題	No.1649 Manhattan Square
ユーザー	Drice27149
提出日時	2021-08-13 22:59:51
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	915 ms / 3,000 ms
コード長	2,934 bytes
コンパイル時間	882 ms
コンパイル使用メモリ	64,640 KB
実行使用メモリ	39,296 KB
最終ジャッジ日時	2024-10-03 22:11:18
合計ジャッジ時間	32,709 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	12 ms 15,744 KB
testcase_01	AC	12 ms 15,616 KB
testcase_02	AC	17 ms 16,128 KB
testcase_03	AC	15 ms 16,128 KB
testcase_04	AC	15 ms 16,128 KB
testcase_05	AC	15 ms 16,256 KB
testcase_06	AC	16 ms 16,128 KB
testcase_07	AC	886 ms 39,296 KB
testcase_08	AC	873 ms 39,040 KB
testcase_09	AC	872 ms 39,040 KB
testcase_10	AC	881 ms 39,040 KB
testcase_11	AC	869 ms 39,040 KB
testcase_12	AC	636 ms 28,416 KB
testcase_13	AC	699 ms 29,952 KB
testcase_14	AC	702 ms 29,824 KB
testcase_15	AC	730 ms 30,720 KB
testcase_16	AC	555 ms 26,112 KB
testcase_17	AC	643 ms 28,416 KB
testcase_18	AC	390 ms 23,040 KB
testcase_19	AC	607 ms 27,264 KB
testcase_20	AC	599 ms 27,264 KB
testcase_21	AC	762 ms 31,872 KB
testcase_22	AC	893 ms 39,168 KB
testcase_23	AC	915 ms 39,296 KB
testcase_24	AC	901 ms 39,168 KB
testcase_25	AC	904 ms 39,168 KB
testcase_26	AC	891 ms 39,168 KB
testcase_27	AC	905 ms 39,040 KB
testcase_28	AC	872 ms 39,168 KB
testcase_29	AC	895 ms 39,168 KB
testcase_30	AC	891 ms 39,168 KB
testcase_31	AC	892 ms 39,296 KB
testcase_32	AC	910 ms 39,296 KB
testcase_33	AC	877 ms 39,296 KB
testcase_34	AC	883 ms 39,168 KB
testcase_35	AC	882 ms 39,296 KB
testcase_36	AC	882 ms 39,296 KB
testcase_37	AC	890 ms 39,168 KB
testcase_38	AC	907 ms 39,168 KB
testcase_39	AC	888 ms 39,296 KB
testcase_40	AC	892 ms 39,296 KB
testcase_41	AC	894 ms 39,296 KB
testcase_42	AC	660 ms 29,824 KB
testcase_43	AC	13 ms 15,872 KB
testcase_44	AC	13 ms 15,872 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード