#685247 (C) No.1649 Manhattan Square

提出ソース

結果

問題	No.1649 Manhattan Square
ユーザー	👑 ygussany
提出日時	2021-08-01 15:52:08
言語	C (gcc 12.3.0)
結果	AC
実行時間	1,416 ms / 3,000 ms
コード長	3,437 bytes
コンパイル時間	386 ms
コンパイル使用メモリ	36,224 KB
実行使用メモリ	10,460 KB
最終ジャッジ日時	2024-04-14 16:10:40
合計ジャッジ時間	47,066 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 7,168 KB
testcase_01	AC	3 ms 8,064 KB
testcase_02	AC	11 ms 7,212 KB
testcase_03	AC	11 ms 7,340 KB
testcase_04	AC	11 ms 7,332 KB
testcase_05	AC	11 ms 7,212 KB
testcase_06	AC	10 ms 8,112 KB
testcase_07	AC	1,402 ms 10,384 KB
testcase_08	AC	1,395 ms 10,400 KB
testcase_09	AC	1,410 ms 10,388 KB
testcase_10	AC	1,405 ms 10,356 KB
testcase_11	AC	1,414 ms 10,392 KB
testcase_12	AC	779 ms 10,304 KB
testcase_13	AC	946 ms 10,264 KB
testcase_14	AC	867 ms 10,324 KB
testcase_15	AC	931 ms 10,336 KB
testcase_16	AC	711 ms 10,412 KB
testcase_17	AC	751 ms 10,432 KB
testcase_18	AC	645 ms 10,288 KB
testcase_19	AC	833 ms 10,300 KB
testcase_20	AC	771 ms 10,452 KB
testcase_21	AC	1,008 ms 10,324 KB
testcase_22	AC	1,400 ms 10,440 KB
testcase_23	AC	1,407 ms 10,408 KB
testcase_24	AC	1,399 ms 10,420 KB
testcase_25	AC	1,410 ms 10,460 KB
testcase_26	AC	1,404 ms 10,324 KB
testcase_27	AC	1,404 ms 10,432 KB
testcase_28	AC	1,404 ms 10,412 KB
testcase_29	AC	1,405 ms 10,416 KB
testcase_30	AC	1,408 ms 10,388 KB
testcase_31	AC	1,411 ms 10,408 KB
testcase_32	AC	1,416 ms 10,256 KB
testcase_33	AC	1,410 ms 10,420 KB
testcase_34	AC	1,414 ms 10,392 KB
testcase_35	AC	1,405 ms 10,432 KB
testcase_36	AC	1,409 ms 10,288 KB
testcase_37	AC	1,406 ms 10,388 KB
testcase_38	AC	1,406 ms 10,356 KB
testcase_39	AC	1,409 ms 10,272 KB
testcase_40	AC	1,406 ms 10,436 KB
testcase_41	AC	1,402 ms 10,260 KB
testcase_42	AC	572 ms 10,456 KB
testcase_43	AC	3 ms 7,552 KB
testcase_44	AC	3 ms 7,552 KB

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

ソースコード

raw source code

#include <stdio.h>

#define SIZE 450
#define NUM 450
const int Mod = 998244353;

typedef struct {
	int key, id;
} data;

void merge_sort(data x[], int n)
{
	static data y[200001] = {};
	if (n <= 1) return;
	merge_sort(&(x[0]), n/2);
	merge_sort(&(x[n/2]), (n+1)/2);
	
	int i, p, q;
	for (i = 0, p = 0, q = n/2; i < n; i++) {
		if (p >= n/2) y[i] = x[q++];
		else if (q >= n) y[i] = x[p++];
		else y[i] = (x[p].key < x[q].key)? x[p++]: x[q++];
	}
	for (i = 0; i < n; i++) x[i] = y[i];
}

int main()
{
	int i, N, x[200001], y[200001];
	data d[200001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d %d", &(x[i]), &(y[i]));

	int j, m, n, X[200001], Y[200001];
	long long ans[2] = {}, sum;
	for (i = 0; i < N; i++) {
		d[i].key = y[i+1];
		d[i].id = i + 1;
	}
	merge_sort(d, N);
	for (i = 0, sum = 0; i < N; i++) {
		j = d[i].id;
		ans[0] += (long long)y[j] * y[j] % Mod * (N - 1) % Mod;
		ans[0] += Mod - sum * y[j] * 2 % Mod;
		sum += y[j];
		while (sum >= Mod) sum -= Mod;
	}
	for (i = 1, n = 0, Y[0] = y[d[0].id], y[d[0].id] = 0; i < N; i = j) {
		for (j = i; j < N && y[d[j].id] == Y[n]; j++) y[d[j].id] = n;
		if (j < N) {
			Y[++n] = y[d[j].id];
			y[d[j++].id] = n;
		}
	}
	n++;
	
	for (i = 0; i < N; i++) {
		d[i].key = x[i+1];
		d[i].id = i + 1;
	}
	merge_sort(d, N);
	for (i = 0, sum = 0; i < N; i++) {
		j = d[i].id;
		ans[0] += (long long)x[j] * x[j] % Mod * (N - 1) % Mod;
		ans[0] += Mod - sum * x[j] * 2 % Mod;
		sum += x[j];
		while (sum >= Mod) sum -= Mod;
	}
	for (i = 1, m = 0, X[0] = x[d[0].id], x[d[0].id] = 0; i < N; i = j) {
		for (j = i; j < N && x[d[j].id] == X[m]; j++) x[d[j].id] = m;
		if (j < N) {
			X[++m] = x[d[j].id];
			x[d[j++].id] = m;
		}
	}
	m++;
	
	int k, l, p_num[200001] = {}, block_num[NUM] = {}, block_add[NUM] = {};
	long long p_sum[200001] = {}, block_xsum[NUM] = {}, block_ysum[NUM] = {}, block_total[NUM] = {};
	k = y[d[0].id];
	l = k / SIZE;
	p_num[k]++;
	block_num[l]++;
	block_ysum[l] = Y[k] % Mod;
	for (i = 1; i < N; i++) {
		if (x[d[i].id] > x[d[i-1].id]) {
			for (j = 0; j <= (n - 1) / SIZE; j++) {
				block_add[j] += X[x[d[i].id]] - X[x[d[i-1].id]];
				block_xsum[j] += (long long)(X[x[d[i].id]] - X[x[d[i-1].id]]) * block_num[j] % Mod;
				if (block_xsum[j] >= Mod) block_xsum[j] -= Mod;
				block_total[j] += (X[x[d[i].id]] - X[x[d[i-1].id]]) * block_ysum[j] % Mod;
				if (block_total[j] >= Mod) block_total[j] -= Mod;
			}
		}
		
		k = y[d[i].id];
		l = k / SIZE;
		if (block_add[l] != 0) {
			for (j = l * SIZE; j < n && j < (l + 1) * SIZE; j++) {
				p_sum[j] += (long long)p_num[j] * block_add[l] % Mod;
				if (p_sum[j] >= Mod) p_sum[j] -= Mod;
			}
			block_add[l] = 0;
		}
		p_num[k]++;
		block_num[l]++;
		block_ysum[l] += Y[k];
		while (block_ysum[l] >= Mod) block_ysum[l] -= Mod;
		for (j = l * SIZE; j < k; j++) {
			ans[1] += (Y[k] - Y[j]) * p_sum[j] % Mod;
			if (ans[1] >= Mod) ans[1] -= Mod;
		}
		for (j++; j < (l + 1) * SIZE && j < n; j++) {
			ans[1] += (Y[j] - Y[k]) * p_sum[j] % Mod;
			if (ans[1] >= Mod) ans[1] -= Mod;
		}
		for (j = 0; j < l; j++) {
			ans[1] += Y[k] * block_xsum[j] % Mod - block_total[j];
			if (ans[1] >= Mod) ans[1] -= Mod;
			else if (ans[1] < 0) ans[1] += Mod;
		}
		for (j++; j <= (n - 1) / SIZE; j++) {
			ans[1] += block_total[j] - Y[k] * block_xsum[j] % Mod;
			if (ans[1] >= Mod) ans[1] -= Mod;
			else if (ans[1] < 0) ans[1] += Mod;
		}
	}
	
	printf("%lld\n", (ans[0] + ans[1] * 2) % Mod);
	fflush(stdout);
	return 0;
}

yukicoder

結果

テストケース

ソースコード